BitCell

Datorii

Iahim încearcă, pe cât posibil, să facă în fiecare zi câte o faptă bună. Astăzi, el s-a gândit că ar fi frumos să își plătească datoriile pe care le are față de unii prieteni. Pentru asta, Iahim a creat o listă care conține atât prietenii care îi sunt îndatorați cât și cei cărora le este dator și a salvat-o în fișierul bitcell13.in respectând următoarele reguli:

• pe fiecare linie a fișierului se află numele unui prieten urmat o sumă de bani; această sumă de bani este un număr întreg din intervalul [-1000,1000] reprezentând suma pe care o datorează unui prieten (dacă este număr negativ) sau suma datorată de un prieten (dacă este număr pozitiv);
• numele unui prieten poate conține doar litere ale alfabetului englezesc și cifre;
• numele prietenilor sunt scurte, cu o lungime de maximum 10 caractere;
  nu vor exista doi prieteni cu același nume
• conține maximum 100 de linii

Acum, Iahim ar vrea să știe dacă poate alege un grup de prieteni astfel încât să-și poată plăti toate datoriile față de cei din grup strângând toți banii de la prietenii din grup care îi sunt datori și să rămână, la final, fără niciun ban.
Dacă există un astfel de grup, se va afișa în fișierul bitcell13.out "DA" iar în caz contrar se va afișa "NU". Se acordă puncte suplimentare dacă în cazul în care răspunsul este "DA" se vor afișa pe următoarele linii din fișier numele prietenilor care fac parte din grup în ordine alfabetică (cerința este opțională).

Exemplu:

bitcell13.in:


bitcell13.out:


Explicație: în cazul de față, Iahim poate lua cei 103 lei cu care Ionuț îi este dator și să-și plătească datoriile de 50, 20 și 33 de lei față de Bogdan, Grigore și respectiv Medana. Afișarea grupului de prieteni este opțională și aduce puncte bonus.

Perioada de desfăşurare:

16-27 August - înscrierea în concurs
28 August - desemnarea câștigătorului

P.S.: Problema este o variantă simplificată a celei cu caloriile de aici. Mulțumesc Smith pentru pontul referitor la problema aia .

Atenție: pentru că a trecut aproape o săptămână și nu a venit nimeni cu o rezolvare, am spus să o simplific modificând limitele datelor de intrare: sumele de bani pe care trebuie să le restituie sau să le primească sunt numere întregi din intervalul [-100,100] și numărul de linii din fișier este de maximum 30.

Am o mica intrebare , in cazul de fata Iahin de ce nu are la dispozitie 303 lei , stransi de la Ionut (103) si Sebi (200) ?

La asta m-am gandit si eu atunci cand am vazut pentru prima oara problema. Explicatia este in enunt: "Iahim ar vrea să știe dacă poate alege un grup de prieteni astfel încât să-și poată plăti toate datoriile față de cei din grup strângând toți banii de la prietenii din grup care îi sunt datori și să rămână, la final, fără niciun ban.". Acel "grup" este explicatia. Deci programul trebuie sa verifice daca se poate forma un grup cu semnificatia de mai sus astfel incat Iahim sa gestioneze banii doar in acel grup (asta inseamna sa preia banii de la cei ce ii sunt datori lui Iahim iar cu toti acesti bani sa-si plateasca toate datoriile din acest grup). Deci trebuie doar verificata existenta acelui grup.

Sper sa nu fiu singurul participant .

Executabilul : http://www.2shared.com/file/CFdxHqai/bitcell.html

^ Oare numai mie nu-mi merge ? (simptom : don't send)

Rezolvarea mea este în ataș. No cookies for me, I guess .

Chiar acum l-am incercat dinou si merge ok , nu imi da eroare.

Executabil : http://www.2shared.com/file/jwdsNdV5/bitcell.html

Sharky cel putin la mine rezolvarea ta nu printeaza "NU" deloc , a lui eni4ever pare ok

Eu sunt cam incepator intr-ale programarii si chiar nu am reusit sa o rezolv, dar ma prind eu dupa ce se termina concursul cum sta treaba

Eu nu prea reusesc sa inteleg problema... Deci , programul ar trebui sa verifice daca Iahim poate restituii banii UNUI SINGUR prieten indatorat lui,unui grup de prieteni ( ceea ce inteleg din exemplu)? Sau...sa verifice daca toti banii primiti sunt egali cu toti banii indatorati...?

Trebuie sa gaseasca un subgrup de prieteni (care ii datoreaza SI carora le datoreaza bani) in asa fel incat, daca isi aduna toti banii de la prietenii care ii sunt datori, poate plati datoriile catre prietenii carora le este dator, fara a ramane cu bani.

Bineinteles, se presupune ca Iahim nu are niciun ban.

And the winner is ?

Probabil nu s-a oferit nimeni sa "jurizeze" concursul iar Mihai este plecat in vacanta pentru ceva timp.

new_luca wrote:Probabil nu s-a oferit nimeni sa "jurizeze" concursul iar Mihai este plecat in vacanta pentru ceva timp.

Foarte probabil.. Pentru cei care au trimis solutii...cum se făcea ? Am avut si eu o idee,dar se lega de backtracking( încă nu ştiu cu ce se mănâncă). Se putea fara ?

^ Puteai să încerci o soluție recursivă dar, după natura problemei (complexitate exponențială), îți rugai neamul din anul 2500 să-ți trimită rezultatul pentru, să zicem, 15 prieteni. Asta considerând că ar mai exista picior de om prin anul acela.

Problema este clasică. Este o variațiune a deja celebrei și totodată dificilei probleme cu rucsacul : problema cu subsume.

Eu am ales sa folosesc metoda BackTracking si pentru 20 de prieteni am avut timp sa imi contactez neamurile din 2500 .

Deocamdată nu am avut timp să mă uit peste soluții așa că nu mă pot pronunța. O să-l rog totuși pe Victor să dea el drumul la un nou concurs (te rog, Victor ;D) urmând ca la acesta să stabilesc câștigătorul atunci când voi prinde ceva timp liber.