Šeštadieninė informatikos olimpiadininkų mokykla

Įmonės įsiskolinusios viena kitai. Jeigu įmonė turėtų pinigų, ji galėtų skolas sumokėti. Tačiau jų neturi. O neturi todėl, kad jai negrąžina skolų kitos įmonės. Kitos įmonės negali sumokėti savų skolų dėl tos pačios priežasties – jos negauna pinigų iš joms skolingų įmonių. Susidaro uždaras ratas. Tačiau jį galima pralaužti. Pasirodo, skolas galima sumokėti ... skolomis.

Sakykime, įmonė A yra skolinga 100 litų įmonei B, įmonė B – 50 litų įmonei C ir įmonė C – 75 litus įmonei A.

Šis sąrašas yra uždaras. Todėl bendra skolų suma gali būti sumažinta, pertvarkius skolų sąrašą taip: įmonė A skolinga 50 litų įmonei B ir įmonė C skolinga 25 litus įmonei A. Įmonės C skola įmonei A gali būti laikoma netiesiogine įmonės C skola įmonei B per įmonę A, todėl galutinis skolų sąrašas yra toks: įmonė A skolinga 25 litus įmonei B ir įmonė C skolinga 25 litus įmonei B.

Užduotis

Parašykite programą, kuri išanalizuotų įmonių skolas ir jas pertvarkytų taip, kad bendra visų įmonių skolų suma būtų mažiausia.

Pradiniai duomenys

Duomenis sudaro skolų sąrašas. Kiekvienas sąrašo elementas įrašytas atskiroje eilutėje ir išreiškiamas trejetu:

čia ir – įmonių kodai, – įmonės skola įmonei .

Pradiniai duomenys tenkina reikalavimus: 1. įmonių kodai yra sveikieji skaičiai iš intervalo ; 2. skolos išreiškiamos teigiamais realiaisiais skaičiais; 3. sąrašo gale yra įrašas, sudarytas iš trijų nulių.

Rezultatai

Rezultatą sudaro: 1. bendra pradinė skolų suma; 2. bendra galutinė skolų suma; 3. skolų sąrašas, gautas pertvarkius skolas; jo elementai turi būti sudaryti iš trijų skaičių taip pat, kaip ir pradinių duomenų sąraše.

Pavyzdžiai

11 22 100.00
22 33  50.00
33 11  75.00
 0  0   0.00

SUMA PRADEDANT:   225.00
 SUMA BAIGIANT:   50.00
 LIKUSIOS SKOLOS:
 11  22  25.00
 33  22  25.00