0341 - Bomboane

Cerinţa

La magazinul din colț au fost aduse n cutii, numerotate de la 1 la n, fiecare conținând un anumit număr de bomboane. Administratorul magazinului hotărăște, pentru bunul mers al afacerilor, că bomboanele trebuie rearanjate în cutii, astfel încât fiecare cutie să conțină același număr de bomboane. Pentru aceasta, administratorul magazinului realizează în mod repetat următoarea operație: mută un număr oarecare de bomboane din cutia cu număr maxim de bomboane în cea cu număr minim de bomboane.

Determinați un șir cu număr minim de operații prin care toate cutiile conțin același număr de bomboane.

Date de intrare

Fişierul de intrare bomboaneIN.txt conţine pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spaţii, reprezentând numărul de bomboane din fiecare cutie.

Date de ieşire

Fişierul de ieşire bomboaneOUT.txt va conţine pe prima linie numărul M, reprezentând numărul total de mutări. Următoarele M linii descriu mutările. Fiecare linie va conține câte trei numere S D B, separate prin câte un spațiu, cu semnificația: din cutia S s-au mutat în cutia D un număr de B bomboane.

Restricţii şi precizări

• 1 ≤ n ≤ 1000
• în fiecare cutie se află cel puțin una și cel mult 1000 de bomboane
• după efectuarea mutărilor numărul total de bomboane din cutii este același cu numărul total de bomboane de la început
• dacă nu este posibilă redistribuirea bomboanelor în condițiile date se va afișa pe prima linie a fișierului valoarea -1
• administratorul magazinului bănuiește că aceasta nu este cea mai eficientă metodă de lucru, dar se mulțumește cu aceasta.

Exemplul 1:

bomboaneIN.txt

5
4 2 1 7 1

bomboaneOUT.txt

3
4 3 2
4 5 2
1 2 1

Explicație

Se fac 3 operații:

• se mută 2 bomboane din cutia 4 în cutia 3. Conținutul cutiilor va fi: 4 2 3 5 1
• se mută 2 bomboane din cutia 4 în cutia 5. Conținutul cutiilor va fi: 4 2 3 3 3
• se mută o bomboană din cutia 1 în cutia 2. Conținutul cutiilor va fi: 3 3 3 3 3

Exemplul 2:

bomboaneIN.txt

1001
4 2 1 7 1

bomboaneOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> INFILE = "bomboaneIN.txt" OUTFILE = "bomboaneOUT.txt"

NMAX = 1000 + 1 VALMAX = 1000 + 1

v = [0] * NMAX p = [0] * NMAX sol = [[0] * NMAX for _ in range(3)]

def check_constraints(n):

   if 1 <= n <= 1000:
       return True
   else:
       with open(OUTFILE, 'w') as outfile:
           outfile.write("Datele nu corespund restrictiilor impuse")
       return False

with open(INFILE, 'r') as infile:

   n = int(infile.readline())
   
   if not check_constraints(n):
       exit()

   v[1:n + 1] = map(int, infile.readline().split())
   p[1:n + 1] = range(1, n + 1)
   sum_val = sum(v[1:n + 1])

   if sum_val % n != 0:
       with open(OUTFILE, 'w') as outfile:
           outfile.write("-1")
       exit()

   ma = sum_val // n
   nr = 0

   while n > 0:
       min_val, max_val = VALMAX, 0
       p1, p2 = 0, 0

       for i in range(1, n + 1):
           if v[i] < min_val:
               min_val = v[i]
               p1 = i
           if v[i] > max_val:
               max_val = v[i]
               p2 = i

       if max_val == ma:
           break

       v[p2] -= ma - v[p1]
       nr += 1
       sol[0][nr] = p[p2]
       sol[1][nr] = p[p1]
       sol[2][nr] = ma - v[p1]
       v[p1] += ma - v[p1]

       v[0] = 0
       for i in range(1, n + 1):
           if v[i] != ma:
               v[0] += 1
               v[v[0]] = v[i]
               p[v[0]] = p[i]

       n = v[0]

   with open(OUTFILE, 'w') as outfile:
       outfile.write(f"{nr}\n")
       for i in range(1, nr + 1):
           outfile.write(f"{sol[0][i]} {sol[1][i]} {sol[2][i]}\n")

</syntaxhighlight>