Šeštadieninė informatikos olimpiadininkų mokykla

Bibliotekoje yra leidinių, kurie susideda iš kelių tomų. Tačiau šie tomai lentynose sumaišyti su kitų leidinių tomais, pavyzdžiui:

image

Skaičiai virš lentynos žymi vietą lentynoje, skaičiai pirmojoje eilutėje rodo leidinio numerį, antrojoje – leidinio tomo numerį.

Knygų tvarkyti bibliotekininkas nenori. Tačiau nori, kad būtų lengviau jas rasti. Tam jis susirado kiekvieno leidinio pirmą tomą, pasižiūrėjo, kiek tomų sudaro leidinį ir įsidėmėjo pirmojo tomo vietą lentynoje, t. y. susidarė lentelę. Aukščiau pateiktam pavyzdžiui lentelė atrodytų šitaip:

Leidinys

Pirmojo tomo vieta

Tomų skaičius

1
2
3
4

1
3
10
11

4
4
2
1

Po to bibliotekininkas sudarė dar vieną lentelę, turinčią tiek elementų, kiek yra vietų lentynoje. Į kiekvieną lentelės elementą įrašė tam tikrą skaičių. Jei vieta lentynoje tuščia, į lentelės elementą įrašė nulį. Jei toje vietoje padėtas kurio nors leidinio tomas, į lentelę įrašė vietą, kurioje padėtas sekantis to paties leidinio tomas. Jei ten padėtas paskutinis kurio nors leidinio tomas, į lentelę įrašomas skaičius: -1.

Mūsų pateiktam pavyzdžiui antroji lentelė atrodo šitaip:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

4 5 6 2 -1 7 9 -1 -1 8 -1 0 0 0

Tokiu būdu bibliotekininkas galėjo lengviau rasti skaitytojo pageidaujamą tomą. Pavyzdžiui, skaitytojas pageidauja gauti antrojo leidinio trečiąjį tomą. Iš pirmos lentelės bibliotekininkas mato, kad pirmasis tomas lentynoje yra trečias. Tada iš antros lentelės trečio stulpelio aišku, kad antrasis tomas bus šeštoje lentynos pozicijoje. O šeštasis stulpelis rodo, kad trečiasis tomas yra septintoje lentynos pozicijoje.

Tačiau kartą prisireikė perrašyti antrąją lentelę. Bibliotekininkas netyčia galėjo padaryti vieną klaidą – įrašyti ne tokį skaičių antroje eilutėje. Bibliotekininkas tikrai žino,kad perrašydamas nulius jokios klaidos nepadarė: kur senoje lentelėje buvo įrašyti nuliai, ten ir perrašytoje lentelėjetikraiyranuliai. Taip pat aišku, kad pakeistasis skaičius yra realus, t.y. jei lentynoje yra 15 vietų knygoms, bibliotekininkas per klaidą negalėjo įrašyti 16 ar didesnio skaičiaus.

Užduotis

Parašykite algoritmą, kuris nustatytų, ar bibliotekininkas padarė klaidą, ir jei taip – ištaisytų ją, jeigu tai įmanoma.

Pradiniai duomenys

Pirmoje eilutėje įrašytas leidinių skaičius . Vieną leidinį sudaro ne daugiau kaip 20 tomų.

Tolesnėse eilučių pateikta pirmoji lentelė. Į kiekvieną eilutę įrašyta po du skaičius: leidinio pirmojo tomo vieta ir leidinio tomų skaičius.

Kitoje eilutėje įrašytas vietų skaičius lentynoje . Toliau eina eilučių, kuriose pateikta antroji lentelė. Kiekvienoje eilutėje įrašyta po vieną skaičių.

Rezultatai

Jeigu klaidos nebuvo, tai spausdinamas pranešimas GERAI. Jei klaida vis dėlto buvo padaryta ir jos pataisyti nepavyksta, spausdinamas pranešimas BLOGAI.

Jei klaidą pataisyti galima, tai spausdinami du skaičiai (vienoje eilutėje, atskirti tarpu). Pirmasis skaičius – tai perrašytos lentelės stulpelis, kur buvo klaida, antrasis – atstatyta reikšmė.

Pavyzdžiai

4 
1 4 
3 4 
10 2 
11 1 
14
4 
5 
6 
2 
-1 
7 
9 
-1 
-1 
8 
-1 
0 
0 
0

GERAI

4 
1 4 
3 4 
10 2 
11 1 
14 
4 
1 
6 
2 
-1
7 
9 
-1 
-1 
8 
-1
0 
0 
0

2 5

Buvo padaryta klaida 2-ame lentelės stulpelyje: penketas pakeistas į vienetą. Todėl susidarė ciklas: pirmas tomas stovi pirmoje pozicijoje, antras – ketvirtoje, trečias – antroje, o ketvirtas – vėl pirmoje.

Ribojimai