.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » datorii

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
datorii


Timp maxim de execuţie / test:
4s
Memorie totala disponibilă / stivă:
16MB / 1MB

Într-un grup de prieteni nu este un lucru ieşit din comun, ca unii să primească bani împrumut de la alţii. Datoriile ce se formează astfel sunt rezolvate ulterior. De exemplu, dacă Gigel îi plăteşte o bere lui Ghiţă, data viitoare va plăti Ghiţă berea pentru amândoi şi datoriile vor fi rezolvate.
Dacă după un timp mai îndelungat împrumuturile nu se rezolvă de la sine, grupul de prieteni se adună pentru a rezolva problemele financiare. La o asemenea întâlnire este de dorit, ca numărul de tranzacţii efectuate să fie minim. De exemplu, dacă Gigel îi datorează lui Ghiţă 10 RON, iar Ghiţă lui Daniel tot 10 RON, este de ajuns ca Gigel să dea 10 RON lui Daniel şi toate datoriile vor fi rezolvate.

Cerinţă

Cunoscând toate împrumuturile ce au fost făcute în grupul de prieteni, determinaţi o modalitate de rezolvare a datoriilor cu număr minim de tranzacţii. Dacă există mai multe posibilităţi cu număr minim de tranzacţii, determinaţi o modalitate pentru care suma totală de bani tranzacţionată să fie minimă. Dacă există mai multe posibilităţi cu număr minim de tranzacţii şi sumă totală de bani minimă, afişaţi oricare dintre acestea.

Date de intrare

Fişierul de intrare datorii.in va conţine pe prima linie două numere naturale separate prin spaţiu N M, reprezentând numărul prieteni din grup, respectiv numărul de împrumuturi făcute. Prietenii sunt numerotaţi de la 1 la N. Următoarele M linii vor conţine câte trei numere naturale separate prin spaţiu A B C cu semnificaţia: ″A trebuie să plătească C RON lui B″.

Date de ieşire

Fişierul de ieşire datorii.out va conţine pe prima linie două numere naturale separate prin spaţiu K S, unde K reprezintă numărul minim de tranzacţii efectuate, iar S suma totală minimă pentru K tranzacţii. Pe următoarele K linii se vor scrie câte trei numere naturale separate prin spaţiu X Y Z cu semnificaţia: X plăteşte Z RON lui Y.

Restricţii

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

Exemple

datorii.indatorii.outExplicaţii
6 5 1 2 10 2 3 10 4 5 5 5 6 5 6 4 5 1 10 1 3 10 S-a efectuat o singură tranzacţie: persoana 1 a dat 10 RON persoanei 3. Suma minimă tranzacţionată este 10 RON.

autor: Prof. Csaba Pătcaş
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot NT 2008: sub, tetris2, kinder, senzori, rev
De acelaşi autor: zeratul, miniasm, 3d, virus, tango, pack
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre flux: matrice2, furtuna, croco, kimberley, trafic, sponsori, monede1, bomboane, algola, trasee, drumuri, magic5, teroristi, universitate, terenuri3d, asfalt1
surse trimise | ajutor