Dan şi George, buni prieteni, vor să plece pe munte cu cortul. Fiecare face cumpărături, adună bagajele apoi se întâlnesc la Dan şi se hotărăsc să împartă cât mai echitabil greutăţile între ei. Ca să nu existe suspiciuni, fac o listă cu toate obiectele pe care trebuie să le ia, le cântăresc apoi decid că distribuţia cea mai eficientă nu poate fi realizată decât cu ajutorul calculatorului (doar n-au absolvit profilul informatică degeaba).
Cerinţă
Cunoscând numărul de obiecte şi greutăţile acestora, să se determine o modalitate de repartizare a obiectelor astfel încât între greutăţile totale pe care le vor transporta cei doi prieteni diferenţa să fie minimă.
Date de intrare
Fişierul text
echitabil.in are următoarea structură:
N
g1 g2… gN
unde:
N reprezintă numărul de obiecte, iar
g1 g2… gN greutăţile celor
N obiecte
Date de ieşire
Fişierul text
echitabil.out are următoarea structură
S1 S2 // greutăţile totale rezultate prin împărţire (
S1 <= S2)
m // numărul de obiecte pe care le va transporta Dan
gi1 gi2 … gim // greutăţile obiectelor pe care le va transporta Dan
p // numărul de obiecte pe care le va transporta George
gj1 gj2 … gjp // greutăţile obiectelor pe care le va transporta George
Restricţii
2 <= N <= 1000, număr natural
1 <= gi <= 50, i = 1,2,..N, numere naturale
m + p <= N
Obiectele nu pot fi tăiate.
Dacă există mai multe soluţii se va afişa una singură.
Exemple
echitabil.in | echitabil.out |
6
4 7 7 17 29 49
| 56 57
2
7 49
4
4 7 17 29
|