Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-06-03 14:06:47.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:datorii2.in, datorii2.outSursăLot 2008 - Piatra Neamt, Baraj1
AutorCsaba PatcasAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.3 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Datorii2

Intr-un grup de prieteni nu este un lucru iesit din comun, ca unii sa primeasca bani imprumut de la altii. Datoriile ce se formeaza astfel sunt rezolvate ulterior. De exemplu, daca Gigel ii plateste o bere lui Ghita, data viitoare va plati Ghita berea pentru amandoi si datoriile vor fi rezolvate. Daca dupa un timp mai indelungat imprumuturile nu se rezolva de la sine, grupul de prieteni se aduna pentru a rezolva problemele financiare. La o asemenea intalnire este de dorit, ca numarul de tranzactii efectuate sa fie minim. De exemplu, daca Gigel ii datoreaza lui Ghita 10 RON, iar Ghita lui Daniel tot 10 RON, este de ajuns ca Gigel sa dea 10 RON lui Daniel si toate datoriile vor fi rezolvate.

Cerinta

Cunoscand toate imprumuturile ce au fost facute in grupul de prieteni, determinati o modalitate de rezolvare a datoriilor cu numar minim de tranzactii. Daca exista mai multe posibilitati cu numar minim de tranzactii, determinati o modalitate pentru care suma totala de bani tranzactionata sa fie minima. Daca exista mai multe posibilitati cu numar minim de tranzactii si suma totala de bani minima, afisati oricare dintre acestea.

Date de intrare

Fisierul de intrare datorii2.in va contine pe prima linie doua numere naturale separate prin spatiu N M, reprezentand numarul de prieteni din grup, respectiv numarul de imprumuturi facute. Prietenii sunt numerotati de la 1 la N. Urmatoarele M linii vor contine cate trei numere naturale separate prin spatiu A B C cu semnificatia: "A trebuie sa plateasca C RON lui B".

Date de iesire

Fisierul de iesire datorii2.out va contine pe prima linie doua numere naturale separate prin spatiu K S, unde K reprezinta numarul minim de tranzactii efectuate, iar S suma totala minima pentru K tranzactii. Pe urmatoarele K linii se vor scrie cate trei numere naturale separate prin spatiu X Y Z cu semnificatia: X plateste Z RON lui Y.

Restrictii

  • 2 ≤ N ≤ 20
  • 1 ≤ M, C ≤ 100

Exemplu

datorii2.indatorii2.out
6 5
1 2 10
2 3 10
4 5 5
5 6 5
6 4 5
1 10
1 3 10

Explicatie

S-a efectuat o singura tranzactie: persoana 1 a dat 10 RON persoanei 3. Suma minima tranzactionata este 10 RON.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?