Rus Marius: Pagină nouă: = 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 oare...

2024-01-07T11:24:20Z

Pagină nouă: = Cerinţa = La magazinul din colț au fost aduse <code>n</code> cutii, numerotate de la <code>1</code> la <code>n</code>, 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 oare...

New page

= Cerinţa =
La magazinul din colț au fost aduse <code>n</code> cutii, numerotate de la <code>1</code> la <code>n</code>, 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 <code>bomboaneIN.txt</code> conţine pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale separate prin spaţii, reprezentând numărul de bomboane din fiecare cutie.

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

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 1000</code>
* în fiecare cutie se află cel puțin una și cel mult <code>1000</code> 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 <code>-1</code>
* administratorul magazinului bănuiește că aceasta nu este cea mai eficientă metodă de lucru, dar se mulțumește cu aceasta.

= Exemplul 1: =
<code>bomboaneIN.txt</code>
5
4 2 1 7 1
<code>bomboaneOUT.txt</code>
3
4 3 2
4 5 2
1 2 1

= Explicație =
Se fac <code>3</code> operații:

* se mută <code>2</code> bomboane din cutia <code>4</code> în cutia <code>3</code>. Conținutul cutiilor va fi: <code>4 2 3 5 1</code>
* se mută <code>2</code> bomboane din cutia <code>4</code> în cutia <code>5</code>. Conținutul cutiilor va fi: <code>4 2 3 3 3</code>
* se mută o bomboană din cutia <code>1</code> în cutia <code>2</code>. Conținutul cutiilor va fi: <code>3 3 3 3 3</code>

== Exemplul 2: ==
<code>bomboaneIN.txt</code>
1001
4 2 1 7 1
<code>bomboaneOUT.txt</code>
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>

0341 - Bomboane - Revision history