| Fişierul intrare/ieşire: | datorii2.in, datorii2.out | Sursă | Lot 2008 - Piatra Neamt, Baraj1 |
| Autor | Csaba Patcas | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 36096 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | datorii2.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.
