Šeštadieninė informatikos olimpiadininkų mokykla

Labirintas yra orientuoto medžio pavidalo. Kiekvienoje labirinto aklavietėje paslėpta po vieną tam tikros vertės brangakmenį.

Labirinte galima eiti tik tolyn nuo įėjimo (t. y. rodyklėmis parodytomis kryptimis). Iš kiekvienos kryžkelės išeina vienas arba daugiau kelių. Į kiekvieną kryžkelę ir aklavietę veda tik vienas kelias. Yra tik vienas įėjimas į labirintą.

Paveiksle pateikto labirinto pavyzdyje kryžkelės pažymėtos skrituliukais, aklavietės – kvadratėliais, kuriuose įrašyta čia paslėpto brangakmenio vertė. Įėjimas į labirintą pažymėtas žvaigždute.

image

Berniukas eina į labirintą pasiimti vieno brangakmenio, suprantama, kuo didesnės vertės. Jį lydi labirinto šeimininkas, kuris nori,kadbūtųpaimtaskuomažesnėsvertės brangakmenis. Berniukas ir šeimininkas susitinka labirinto įėjime. Kiekvienoje kryžkelėje reikia pasirinkti, kuriuo keliu bus keliaujama toliau (aišku, jei yra daugiau kaip vienas kelias). Įėjime renkasi berniukas, kitoje kryžkelėje (į kurią abu pateko po berniuko pasirinkimo) – šeimininkas, dar kitoje – vėl berniukas ir taip toliau. Ir berniukas ir šeimininkas labai gerai žino labirintą, tad bet kurioje kryžkelėje kiekvienas jų gali pasirinkti, kuriuo labirinto keliu jiems naudingiausia eiti.

Užduotis

Parašykite algoritmą, kuris nustatytų, kokios vertės brangakmenį paims berniukas, jeigu berniukas ir šeimininkas vaikščios optimaliai.

Pradiniai duomenys

Pirmoje eilutėje pateikiamas kryžkelių skaičius ir aklaviečių skaičius . Visada yra bent viena kryžkelė (įėjimas) ir bent viena aklavietė. Skaičių ir suma neviršija 10000. Kryžkelėms yra duoti unikalūs numeriai (sveiki skaičiai) iš intervalo .

Toliau įrašyta eilučių. Kiekviena eilutė nusako arba kryžkelę, arba aklavietę. Šios eilučių pateiktos bet kokia tvarka.

Kryžkelę nusakanti eilutė prasideda raide „K“. Jei ši kryžkelė yra labirinto įėjimas, tuomet po raidės „K“ eina nulis (0), jei į ją patenkama iš kitos kryžkelės, tuomet rašomas pastarosios numeris. Paskutinysis skaičius eilutėje – kryžkelės numeris.

Kiekviena aklavietę nusakanti eilutė prasideda raide „A“. Toliau įrašyti du sveikieji skaičiai: kryžkelės, iš kurios ateinama į šią aklavietę numeris bei joje esančio brangakmenio vertė ( – sveikasis skaičius).

Pradiniuose duomenyse tarp raidės ir po jos esančio skaičiaus bei tarp dviejų skaičių palikta po vieną tarpą.

Pavyzdžiai:

1. Jei aprašoma kryžkelė, kurios numeris 3, o į ją ateinama iš 5–os kryžkelės, tai eilutė atrodys: K 5 3
2. Jei aprašomas įėjimas į labirintą, kuriam suteiktas numeris 4, tai eilutė bus: K 0 4
3. Jei į aklavietę ateinama iš kryžkelės kurios numeris 2, o aklavietėje paslėpto brangakmenio vertė 4, tai eilutė bus: A 2 4.

Rezultatai

Rezultatas yra vienas sveikasis skaičius.

Pavyzdžiai

8 9 
K 10 9 
K 4 7 
A 9 5 
K 5 3 
A 3 3 
A 1 8 
K 0 4 
A 2 4 
K 4 5
K 4 10 
A 1 7 
A 3 2 
K 7 1 
A 3 4 
A 9 8 
K 10 2 
A 7 5

5

image

Ribojimai