Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1993_3e2_valiutos.in

Rezultatų failas: lmio_1993_3e2_valiutos.out

Jei norite pateikti savo sprendimą - prisijunkite.

Valiutos keitimas

N valstybių turi skirtingas valiutas. Kiekvienos valstybės bankas perka kitų valstybių valiutą ir moka už ją sava valiuta.

Valiutų supirkimo kainos pateiktos N\\timesN dydžio lentelėje: i eilutės j stulpelyje nurodoma i valstybės valiutos vieneto kaina j valstybės valiuta. Nulis rodo, kad j valstybė i valstybės valiutos neperka.

Turėdami tam tikrą pradinės valstybės valiutos kiekį ir aplankę kelias valstybes, kiekvienoje jų keisdami valiutą, vėl grįžtame į pradinę valstybę. Jei grįžę turėsime daugiau valiutos, negu jos buvome pasiėmę iš pradžių, tai reikš, kad maršrutas pelningas. Kelionės išlaidos neskaičiuojamos

Reikia nustatyti, ar yra bent vienas pelningas valiutų keitimo maršrutas.

Užduotis

Parašykite programą, kuri atliktų šitokius veiksmus:

  1. perskaitytų valiutų supirkimo kainų lentelę
  2. rastų bent vieną pelningą maršrutą; jei tokio maršruto nėra, išvestų pranešimą: NERASTA
  3. jei pelningas maršrutas yra, parodytų ekrane visų aplankytų valstybių numerius ir pelno, kuris gaunamas nukeliavus tuo maršrutu vieną kartą, dydį procentais.

Pradiniai duomenys

Pirmoje eilutėje nurodytas valstybių skaičius N, t. y. lentelės dydis. Kitose eilutėse pateikta pati lentelė, t. y. N eilučių, kurių kiekvienoje yra po N realiųjų skaičių – valiutos supirkimo kainos.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
2
0.0 2.0
0.5 0.0
 
NERASTA
 
4
0.0 0.0 1.3 1.0
1.2 0.0 0.0 0.0
0.0 1.1 0.0 0.8
0.01 1.0 0.0 0.0
 
PELNINGAS: 1 3 2 
PELNAS: 71.6%

Ribojimai

2\\leqn\\leq10