Słowa 2
Limit pamięci: 64 MB
Niniejsze zadanie to istotnie trudniejsza wersja zadania
Słowa z finału XVI OI.
Nie wystąpiła ona w samym konkursie, a stanowi jedynie rozszerzenie dla tych, którym
po zadaniu "Słowa" jeszcze mało :-).
Niech będzie funkcją określoną na napisach złożonych z cyfr 0 i 1.
Funkcja przekształca napis , zastępując (niezależnie i równocześnie) każdą cyfrę
0 przez 1 i każdą cyfrę 1 przez napis .
Na przykład ,
(tzn. funkcja zastosowana do pustego napisu jest pustym napisem).
Zauważmy, że jest różnowartościowa.
Przez oznaczmy -krotne złożenie funkcji ze sobą.
W szczególności, to funkcja identycznościowa .
Interesują nas napisy postaci dla
Oto kilka pierwszych takich napisów:
,
,
,
,
,
.
Mówimy, że napis
jest
podsłowem napisu
, jeżeli występuje w nim jako
spójny (tj. jednokawałkowy) podciąg.
Mamy dany ciąg liczb naturalnych
.
Celem zadania jest sprawdzenie, czy napis postaci
jest podsłowem
dla pewnego
, a jeżeli tak, to
wyznaczenie najmniejszego takiego
.
Przy tym operacja
oznacza sklejenie (konkatenację) napisów.
Wejście
Pierwszy standardowego wejścia zawiera jedną liczbę całkowitą , .
W drugim wierszu znajduje się nieujemnych liczb całkowitych
() pooddzielanych pojedynczymi odstępami.
Wyjście
Twój program powinien wypisać na standardowe wyjście wiersz zawierający najmniejszą
taką liczbę całkowitą nieujemną , dla której
jest podsłowem , lub jedno słowo NIE, jeżeli żadne takie
nie istnieje.
Przykład
Dla danych wejściowych:
2
1 2
poprawną odpowiedzią jest:
4
natomiast dla danych wejściowych:
2
2 0
poprawnym wynikiem jest:
NIE
Wyjaśnienie do przykładu:
Słowo z pierwszego testu to - jest ono podsłowem
słowa .
W drugim teście występuje słowo , które nie jest
podsłowem żadnego słowa postaci .
Autor zadania: Bartosz Walczak.