Editing 2236 - swap01

Sursa: [https://www.pbinfo.ro/probleme/2236/swap01 2236 - swap01]
----
Se consideră un șir binar a[1], a[2], …, a[n]. Asupra șirului se poate efectua operația swap(i, j) prin care se interschimbă valorile a[i] și a[j].


== Cerinţa ==
Să se determine numărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir.


== Date de intrare ==
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații reprezentând elementele șirului binar.


== Date de ieșire == 
Programul va afișa pe ecran numărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 100.000
== Exemplu ==
; Intrare
: 14
: 1 0 0 1 0 1 1 0 1 0 0 0 1 0
; Ieșire
: 2

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 2236 - swap01

def citire_lista():
    n = int(input())
    lista = input().split()
    lista = [int(x) for x in lista]
    return lista

def numara_unu(lista):
    pozitii_unu = []
    for i in range(len(lista)):
        if lista[i] == 1:
            pozitii_unu.append(i)
    return len(pozitii_unu), pozitii_unu

def calculeaza_swap(lista, pozitii_unu):
    nr_unu, pozitii_unu = numara_unu(lista)
    nr_grupuri = len(pozitii_unu)
    start = pozitii_unu[0]
    end = pozitii_unu[-1]
    for i in range(nr_grupuri):
        if pozitii_unu[i] - i != start:
            start = pozitii_unu[i]
        if end - pozitii_unu[-i-1] != i:
            end = pozitii_unu[-i-1]
    return nr_grupuri - (end - start + 1)

if __name__ == "__main__":
    lista = citire_lista()
    nr_unu, pozitii_unu = numara_unu(lista)
    print(calculeaza_swap(lista, pozitii_unu))

</syntaxhighlight>
== Explicatie Rezolvare ==
Pentru a rezolva această problemă, putem parcurge șirul și să numărăm câte elemente de 1 sunt și unde se află acestea. După aceea, putem verifica în câte părți separate trebuie împărțit șirul (adică câte grupuri separate de 1 sunt) și putem calcula numărul de operații swap necesare pentru a muta fiecare grup la poziția corectă.

Pentru a implementa această soluție, vom crea trei funcții:

citire_lista(): Această funcție va citi de la tastatură numărul de elemente din șir și apoi elementele șirului. Funcția va returna lista citită.
numara_unu(lista): Această funcție va primi lista citită ca parametru și va returna un tuplu cu numărul de elemente de 1 din listă și o listă cu pozițiile acestora.
calculeaza_swap(lista, pozitii_unu): Această funcție va primi lista citită și lista cu pozițiile elementelor de 1. Funcția va determina în câte grupuri trebuie împărțit șirul și va calcula numărul de operații swap necesare pentru a muta fiecare grup la poziția corectă. Funcția va returna numărul total de operații swap necesare.
La final, vom avea un bloc if __name__ == "__main__": în care vom apela cele trei funcții și vom afișa rezultatul.