Podjela
Ceh farmera proizveo je neku ukupnu količinu žita te ga dostavio velikoj prehrambenoj tvrtki. Za obavljen posao tvrtka je svakom od N farmera poštom dostavila jednak iznos od X kuna. Farmeri znaju da nisu svi proizveli jednaku količinu žita te žele poštenije raspodijeliti dobiveni novac. Svi farmeri žive u različitim selima. Sela su povezana cestama tako da od svakog sela postoji jedinstven put do svakog drugog sela. U jednoj transakciji neki farmer svojim traktorom posjeti selo susjedno svojem te osobno uruči drugom farmeru proizvoljan iznos novca. Za svakog farmera poznat je iznos koji je on zaslužio. Potrebno je odrediti:
a) Najmanji broj transakcija potreban da svaki farmer dobije zasluženi iznos.
b) Redoslijed tih transakcija. Pri odreñivanju redoslijeda transakcija potrebno je paziti da farmer ne može dati drugom farmeru veći iznos no što ga trenutno posjeduje.
Moguće je da je tvrtka preplatila posao, tj. ukupno platila više nego što farmeri potražuju; u tom slučaju farmerima je svejedno kako će biti raspodijeljen višak, dok svaki od njih dobije barem onoliko koliko je zaslužio.
U drugom redu nalazi se cijeli broj X (0 ≤ X ≤ 10000), iznos koji je uplaćen svakom farmeru. U trećem redu nalazi se niz od N cijelih brojeva, iznosi koje su farmeri zaslužili. Zbroj ovih iznosa bit će najviše N<X. Sljedećih N−1 redova sadrži opise cesta. Svaka cesta opisana je parom brojeva između 1 i N, oznakama sela koja ta cesta povezuje.
], koja označava da farmer iz sela A predaje farmeru iz sela B iznos od C kuna. Raspored transakcija ne mora biti jedinstven. [c]5
1
0 2 2 0 1
1 2
1 3
3 4
3 5
Izlaz
2
1 2 1
4 3 1 Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.