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.
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 . Przy tym operacja oznacza sklejenie (konkatenację) napisów.Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą , , oznaczającą liczbę przypadków testowych do rozważenia. Pierwszy wiersz opisu każdego przypadku zawiera jedną liczbę całkowitą , . W drugim wierszu opisu znajduje się nieujemnych liczb całkowitych pooddzielanych pojedynczymi odstępami. Suma liczb z drugiego wiersza każdego przypadku jest nie większa niż .
Twój program powinien wypisać na standardowe wyjście wierszy, po jednym dla każdego przypadku testowego. Wiersz odpowiadający danemu przypadkowi testowemu powinien zawierać jedno słowo: TAK - jeśli w tym przypadku jest podsłowem dla pewnego , lub NIE w przeciwnym razie.
Dla danych wejściowych:
2 2 1 2 2 2 0
poprawną odpowiedzią jest:
TAK NIE
Wyjaśnienie do przykładu: Słowo z pierwszego przypadku testowego to - jest ono podsłowem na przykład słowa . W drugim przypadku testowym występuje słowo , które nie jest podsłowem żadnego słowa postaci .
Autorzy zadania: Wojciech Rytter, Bartosz Walczak.