Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTWPZ081 - PTwPZ Bakterie

Bakterie

Treść

Profesor Ciekawski porzucił ostatnimi czasy nauki ścisłe i zajął się mikrobiologią. W swoim tajnym laboratorium w podziemiach Politechniki Białostockiej zajmuje się hodowlą bakterii. Dzięki starannie prowadzonej selekcji genetycznej oraz szczególnym właściwościom wody w kranach Politechniki, udało mu się uzyskać nowy gatunek, Policteria. Bakterie te nie rozmnażają się jak wiele innych organizmów jednokomórkowych. Liczba bakterii w kolonii jest stała i zależy od podgatunku. Podgatunki te profesor oznaczył symbolami K-1, K-2, K-3, itd. Co więcej całkowita masa kolonii jest stała, a pojedyncza bakteria może ważyć dokładnie 1,2,3,… lub 9 jednostek. Dzięki tym właściwościom każdą kolonię można przedstawić jako K-cyfrową liczbę, zwaną liczbą P. Po licznych eksperymentach profesor odkrył, że liczby P dla kolejno następujących po sobie pokoleń bakterii stanowią ciąg rosnący o możliwie najmniej zmieniających się wartościach. Pierwsze pokolenie jest zawsze uzyskiwane sztucznie, natomiast po osiągnięciu maksymalnej możliwej liczby P, kolonia przestaje ewoluować. Przykładowo, jeżeli liczba P pierwszego pokolenia podgatunku K-3 wynosi 213, kolejne pokolenia będą reprezentowane przez liczby 222, 231, 312, 321 i 411.

W celu zbadania dynamiki przeistaczania się kolonii, profesor Ciekawski w określonych odstępach czasu zmierzył masy poszczególnych bakterii, otrzymując w ten sposób liczby P. Teraz na podstawie zebranych danych chciałby wiedzieć, które z kolei pokolenia reprezentują wyniki pomiarów. To zadanie powierzył Tobie, swemu najbardziej zaufanemu asystentowi. Napisz program, który na podstawie liczb P dla pierwszego i nieznanego, badanego pokolenia obliczy, które to z kolei pokolenie.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zestawu danych zawiera liczbę całkowitą k (2<=k<=100) oznaczającą podgatunek bakterii. Drugi wiersz zawiera k-cyfrową liczbę P pierwszego pokolenia bakterii. Trzeci wiersz zawiera k-cyfrową liczbę P definiującą badane pokolenie.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest numer badanego pokolenia bakterii. Dane wejściowe są tak dobrane, że numer ten nie przekracza 1015.

Przykład

dane wejściowe:
2
2
38
74
3
213
411

wynik:
5
6

 


Dodane przez:Michael Suchacz
Data dodania:2009-07-24
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Pochodzenie:Podlaski Turniej w Programowaniu Zespołowym
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.