Županijska razina 2019 / Osnovna škola (7. razred) - 2. zadatak

Evo jedne od onih pitalica koje obično počinju rečenicom: „Jeste li znali da samo 3% osoba na svijetu zna odgovor na ovo pitanje“. Zadan je slijed brojeva: 11, 21, 1211, 111221, 312211, 13112221, 1113213211. Znaš li ti koji je broj sljedeći u slijedu?

Bio je ovo primjer „pogledaj i reci“ slijeda brojeva (engl. look-and-say sequence). Prvi broj slijeda unaprijed je zadan. Sljedeći broj dobije se iz prethodnog tako da redom čitamo njegove znamenke, a prije svake još kažemo koliko ih je uzastopnih.

Npr., prvi broj slijeda je 11. Drugi je 21 što ustvari znači „dvije uzastopne jedinice“. Treći broj je 1211 što znači „jedna dvojka, jedna jedinica“. Četvrti broj je 111221 što znači „jedna jedinica, jedna dvojka i dvije jedinice“.

Napiši program koji za zadani dvoznamenkasti broj \(X\), početni broj slijeda, ispisuje \(N\)-ti po redu broj u slijedu.

Dodatno, program treba za dani broj \(Y\) iz nekog drugog „pogledaj i reci“ slijeda, odrediti dvoznamenkasti broj koji je bio prvi u tom slijedu. Ako postoji više takvih brojeva ispiši najmanji. Garantiramo da će rješenje postojati i da će svi brojevi koji se pojavljuju u tom slijedu prije broja \(Y\) u dekadskom zapisu imati najviše 100 znamenki.

Ulazni podaci

U prvom retku nalazi se prirodan broj \(X\) \((10 ≤ X ≤ 99)\), broj iz teksta zadatka. U drugom retku nalazi se prirodan broj \(N\) \((1 ≤ N ≤ 20)\), broj iz teksta zadatka. U trećem retku nalazi se prirodan broj \(Y\) \((1 ≤ Y ≤ 10^{100}-1)\), broj iz teksta zadatka.

Izlazni podaci

U prvi redak treba ispisati \(N\)-ti po redu broj iz slijeda koji počinje s \(X\). U drugi redak treba ispisati dvoznamenkasti broj, početni broj slijeda u kojem se može naći broj \(Y\).

Bodovanje

Točan ispis prvog retka vrijedi 3 boda, a točan ispis drugog retka 2 boda za svaki test podatak

Test podaci

Ulaz

11
6
1113213211

Izlaz

13112221
11

Ulaz

95
1
13211321322113

Izlaz

95
13

Objašnjenje drugog primjera:

Prvi broj slijeda koji počinje s 95 je očito 95. Slijed kojem je prvi broj 13 sadrži broj 13211321322113. Taj slijed izgleda ovako: 13, 1113, 3113, 132113, 1113122113, 311311222113, 13211321322113.

Ulaz

17
5
132117

Izlaz

1113122117
17