2236 - swap01

Sursa: 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>

1. 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.