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:
,
,
,
,
,
.
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.
<Wyślij rozwiązanie> [0/100]