W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.Pierwszy standardowego wejścia zawiera jedną liczbę całkowitą , . W drugim wierszu znajduje się nieujemnych liczb całkowitych () pooddzielanych pojedynczymi odstępami.
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.
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.