2406 - Sort

Primăria orașului ONI a făcut un contract cu firma Gigel.SRL în vederea amenajării gardului Grădinii Botanice. Șeful firmei a constatat că gardul cu pricina este format doar din trei tipuri de scânduri care sunt aranjate fără nicio regulă. Fiind un tip cu “gust estetic” și-a propus să rearanjeze scândurile astfel încât gardul să conțină scândurile grupate astfel: primele să fie scândurile de primă dimensiune (cea mai mică) apoi cele mijlocii, iar ultimele să fie cele de dimensiunea cea mai mare. Echipa care a fost desemnată să execute lucrarea are un singur muncitor care dorește să știe care este numărul minim de schimbări pe care ar trebui să le facă astfel încât să rezolve problema și scândurile să fie ordonate așa precum a decis șeful firmei. Operația de schimbare constă în alegerea a două scânduri diferite și așezarea uneia în locul celeilalte.

Cerința

Dându-se un număr n ce reprezintă numărul de scânduri care alcătuiesc gardul, precum şi modul în care sunt aranjate scândurile în gard, să se determine care este numărul minim de schimbări ce trebuie realizat astfel încât gardul să aibă scândurile aranjate crescător. Scândurile sunt codificate în funcție de dimensiune prin valorile 1, 2 și 3.

Date de intrare

Fișierul de intrare sort.in conține pe prima linie un număr natural n. Pe a doua linie sunt n valori 1, 2 sau 3 separate prin câte un spațiu ce reprezintă modul de așezare a scândurilor în gardul grădinii.

Date de ieșire

Fișierul de ieșire sort.out va conţine un număr care reprezintă numărul minim de schimbări ce trebuie realizate pentru a aranja gardul astfel încât să fie ordonat crescător.

Restricții și precizări

• 1 ≤ n ≤ 1001

Exemplu:

sort.in

10
1 3 1 2 2 3 1 3 2 1

sort.out

3

Explicație

se realizează schimbarea valorilor de pe pozițiile 2 cu 10, apoi 4 cu 7 și 6 cu 9. Astfel va rezulta succesiv:

1 1 1 2 2 3 1 3 2 3

1 1 1 1 2 3 2 3 2 3

1 1 1 1 2 2 2 3 3 3

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1"> ​import numpy as np

n = 0

t = np.zeros(4, dtype=int)

a = np.zeros(1005, dtype=int)

def Citire():

   global n, t, a

   i = 0

   with open("sortin.txt", "r") as fin:

       n = int(fin.readline())

       for i in range(n):

           a[i] = int(fin.readline())

           t[a[i]] += 1

def Rezolvare():

   global n, t, a

   ans = 0

   s12 = s21 = s13 = s31 = s23 = s32 = 0

   for i in range(t[1]):

       if a[i] == 2:

           s12 += 1

       if a[i] == 3:

           s13 += 1

   for i in range(t[1], t[1] + t[2]):

       if a[i] == 1:

           s21 += 1

       if a[i] == 3:

           s23 += 1

   for i in range(t[1] + t[2], t[1] + t[2] + t[3]):

       if a[i] == 1:

           s31 += 1

       if a[i] == 2:

           s32 += 1

   ans = min(s12, s21) + min(s13, s31) + min(s23, s32) + 2 * (max(s12, s21) - min(s12, s21))

   with open("sortout.txt", "w") as fout:

       fout.write(str(ans) + "\n")

if __name__==__'main'__:

Citire()

Rezolvare()

</syntaxhighlight>