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ă.