Komputery Trzybitowe kontratakują
Limit pamięci: 32 MB
Po ogromnej klapie, jaką okazały się Komputery Trzybitowe (KTB),
naukowcy Bajtlandii mają nowy wspaniały pomysł: Kwantowe
Komputery Trzybitowe (KKTB). Komputery KTB należy potraktować jako
zwyczajną rozgrzewkę przed prawdziwym wyzwaniem - KKTB.
Przewiduje się, że nowe komputery kwantowe będą miały
niespotykaną dotąd moc, bla, bla, bla, wiele głupawych problemów
na olimpiady, bla, bla, bla. Do rzeczy.
Tak jak poprzednio, podstawową trudnością jest inicjalizacja
pamięci. W przypadku komputerów kwantowych problemy są jednak
zupełnie innej natury. Wszystkie operacje wykonywane na elementach
KKTB mają efekty uboczne, tzn. wpływają na inne elementy
komputera. Neutralizowanie tych efektów jest bardzo kosztowne,
dlatego inicjalizacja pamięci bit po bicie nie jest
możliwa. Istnieje jednak inne podejście do problemu, a mianowicie
sterowane impulsy o średnim zasięgu (SISZ). Naukowcy potrafią
wygenerować impulsy, których wpływ na każdy z bitów pamięci
KKTB może być dokładnie obliczony. Impulsy te można emitować
bardzo szybko, więc użycie nawet dużej liczby impulsów jest
bardziej opłacalne niż inicjalizacja pamięci bit po
bicie. Powstaje pytanie, czy da się wyzerować całą pamięc przy
pomocy SISZ. Twoim zadaniem jest napisanie programu, który odpowie
na to pytanie.
Bardziej formalnie, każdy bit pamięci może być w jednym z
stanów ponumerowanych . Impuls SISZ oddziaływuje na
wszystkie bity w ten sam sposób, a zatem można go traktować jak
funkcję . Na
przykład, oznacza, że po wyemitowaniu impulsu ,
wszystkie bity będące w stanie przejdą w stan . Naukowcy
potrafią emitować pewną liczbę impulsów . Twoim
zadaniem jest stwierdzić, czy istnieje ciąg impulsów, który
sprowadza wszystkie bity do stanu (zeruje je), niezależnie od
ich stanu początkowego.
Zadanie
Napisz program, który:
- wczytuje opis dostępnych impulsów,
- sprawdza, czy możliwe jest wyzerowanie pamięci,
- zapisuje odpowiedź do pliku wyjściowego.
Wejście
Każdy test składa się z pewnej liczby zestawów
danych. Pierwszy wiersz standardowego wejścia zawiera pojedynczą
liczbę naturalną , , liczbę zestawów
danych. W dalszej części wejścia znajdują się zestawy
danych. Opis pojedynczego zestawu danych rozpoczyna się wierszem
zawierającym dwie liczby naturalne , , (, ), gdzie jest liczbą różnych stanów bitu, a
liczbą dostępnych impulsów. Kolejnych wierszy zawiera opisy
impulsów, -ty wiersz zawiera opis -tego impulsu. Opis impulsu
jest ciągiem liczb całkowitych ,
opisujących wpływ na stan każdego z bitów pamięci. Liczby
te są pooddzielane pojedynczymi odstępami.
Wyjście
Na standardowe wyjście należy wypisać wierszy, po jednym
dla każdego zestawu danych. -ty wiersz powinien składać się z
pojedynczego słowa TAK, jeśli wyzerowanie pamięci jest dla
-tego testu możliwe, lub NIE w przeciwnym przypadku.
Przykład
Dla danych wejściowych:
2
5 2
1 2 3 4 0
2 3 4 0 1
5 2
1 2 3 4 0
3 3 4 0 1
poprawną odpowiedzią jest:
NIE
TAK
Zapożyczenie z CPSPC: Marcin Mucha.