Clasa a X-a
Ziua 1
Problema 1
La monetarie
Intr-un depozit al monetriei statului sosesc n saci cu monezi. Seful
depozitului cunoaste numarul de monezi din fiecare sac si ar vrea sa modifice
continutul sacilor, prin mutari de monezi dintr-un sac in altul, astfel incāt
in final, in fiecare sac sa fie acelasi numar de monezi. Ajutati seful
depozitului sa obtina acelasi numar de monezi in fiecare sac, prin efectuarea
unui numar minim de mutari.
Date de intrare:
In fisierul text MONEZI.IN se va scrie pe prima linie un numar intreg n
(2<=n<=2000), reprezentānd numarul de saci. Pe urmatoarele n linii sunt scrise
numere intregi, reprezentānd numerele de monezi din fiecare sac (numarul total
de monezi din toti sacii<=1.000.000.000).
Date de iesire:
Rezultatele se vor scrie in fisierul text MONEZI.OUT sub urmatoarea
forma:
- Pe prima linie se scrie un numar intreg m, reprezentānd numarul minim de
mutari necesare.
- Pe urmatoarele m linii se vor scrie triplete de numere intregi:
a b c
unde:
a reprezinta numarul de ordine al sacului din care se muta monezi;
b reprezinta numarul de ordine al sacului in care se muta monezi;
c reprezinta numarul de monezi care se muta din sacul a in sacul b.
Observatie:
In cazul in care problema nu are solutie, se va scrie in fisier cuvāntul:
'NU'.
Exemplu:
MONEZI.IN
3
35
48
37
MONEZI.OUT
2
2 1 5
2 3 3
Timp maxim de executare/test: 8 secunde
Punctaj maxim: 20 puncte