Vizualizare sursă pentru „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 == 
Dacă datele sunt introduse corect, pe ecran se va afișa: 
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''umă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''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

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


== Exemplu 2 ==
; Intrare
: 2 3 5
: 1 1 1 0 0 0 1 0 0 1 1 0 1 1 1
; Ieșire
: Datele nu corespund restricțiilor impuse.


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

def validate_input(n, arr):
    if not (1 <= n <= 100000):
        return False
    if len(arr) != n:
        return False
    return True


def count_swaps(n, arr):
    if not validate_input(n, arr):
        return "Datele nu corespund restricțiilor impuse."

    # Determinăm numărul de valori de 1 din șir
    count_ones = arr.count(1)

    # Numărul minim de operații swap este diferența dintre lungimea șirului și numărul de valori de 1
    min_swaps = n - count_ones

    return min_swaps


if __name__ == "__main__":
    n = int(input())
    arr = list(map(int, input().split()))

    result = count_swaps(n, arr)
    print(result)


</syntaxhighlight>
== Explicatie Rezolvare ==
Avem funcția validate_input care verifică dacă datele de intrare sunt valide. Verificăm dacă n se află în intervalul [1, 100000] și dacă lungimea listei arr este egală cu n.

Funcția principală count_swaps primește numărul de elemente n și lista arr ca argumente. În primul rând, verificăm validitatea datelor de intrare folosind funcția validate_input. Apoi, numărăm numărul de valori de 1 din șir utilizând metoda count a listei. Numărul minim de operații swap este diferența dintre lungimea șirului n și numărul de valori de 1 count_ones.

În blocul if __name__ == "__main__":, citim valorile de intrare n și arr folosind funcția input(). Apoi apelăm funcția count_swaps și afișăm rezultatul.