Komputery trzybitowe
Limit pamięci: 32 MB
Naukowcy w Królestwie Bajtlandii postanowili stworzyć nowy rodzaj
komputerów, a mianowice komputery trzybitowe (KTB). Powszechnie
uważa się, że ten nowy rodzaj komputerów pozwoli rozwiązać
wiele problemów zbyt trudnych dla klasycznych
komputerów. Niestety, w trakcie prac naukowcy napotkali wiele
trudności technicznych. Twoim zadaniem jest pomóc im w
przezwyciężeniu jednej z nich.
Naukowcy zajmują się aktualnie procedurami inicjalizacji pamięci
komputera. Komputer KTB posiada bitów pamięci ponumerowanych
liczbami . Każdy bit może przyjmować jedną z trzech
wartości lub być w stanie niezainicjalizowanym. Komputer
KTB udostępnia następujące operacje inicjalizujące:
- dwóm kolejnym niezainicjalizowanym bitom można przypisać
dwie różne wartości,
- dwóm kolejnym bitom, z których jeden jest
niezainicjalizowany, a drugi ma wartość , można przypisać
dwie różne wartości, przy czym obie muszą być różne od .
Oto przykładowa sekwencja inicjalizacji pamięci dla
:
, gdzie
oznacza bit niezainicjalizowany.
Zadanie
Napisz program, który:
- wczyta wartości, którymi ma być zainicjalizowana pamięć,
- sprawdzi czy taka inicjalizacja jest możliwa,
- wypisze znalezioną odpowiedź.
Wejście
Standardowe wejście może zawierać opisy od do
konfiguracji pamięci, które chcemy uzyskać. Pierwszy wiersz
wejścia zawiera pojedynczą liczbę całkowitą - liczbę
konfiguracji. W kolejnych wierszach znajdują się opisy
konfiguracji. Opis jednej konfiguracji składa się z dwóch
wierszy. Pierwszy wiersz zawiera pojedynczą liczbę całkowitą
, , rozmiar pamięci dla -tej
konfiguracji. Drugi wiersz zawiera ciąg długości
składający się z liter - ciąg ten opisuje
konfigurację, którą chcemy uzyskać.
Wyjście
Standardowe wyjście powinno zawierać wierszy, po
jednym dla każdej konfiguracji pamięci. -ty wiersz powinien
zawierać pojedyncze słowo TAK, jeśli inicjalizacja jest
możliwa, w przeciwnym przypadku NIE.
Przykład
Dla danych wejściowych:
2
4
aaab
4
aabb
poprawną odpowiedzią jest:
TAK
NIE
Zapożyczenie z CPSPC: Piotr Sankowski.