Korekcja błędów
Limit pamięci: 32 MB
Alicja i Bob, stali bohaterowi książek o kryptografii, ustalili algorytm szyfrowania, wymienili klucze i zastanawiają się nad sposobem przesyłania zaszyfrowanych wiadomości (dalej krótko wiadomości) po dostępnym dla nich łączu.
Wiadomość jest ciągiem małych liter alfabetu angielskiego.
Alicja i Bob postanowili zastosować kod binarny.
Przypisali każdej literze pewien ciąg bitów.
Nie zakładali przy tym stałej długości tych ciągów, ani tego, że żaden ciąg nie jest prefiksem innego.
Może się więc zdarzyć, że nie każdą zakodowaną wiadomość da się jednoznacznie zdekodować.
Wiadomo natomiast, że ciągi bitów przypisane różnym literom są różne.
Ciąg bitów będący zakodowaną wiadomością składa się z połączonych ciągów odpowiadających kolejnym literom tej wiadomości.
Twoim zadaniem jest napisanie dla Alicji i Boba programu dekodującego otrzymane ciągi bitów.
Powiemy, że wiadomość odpowiada ciągowi bitów , jeśli
i zakodowana wiadomość są tej samej długości i różnią się co najwyżej wartością jednego bitu.
Jeśli tylko jedna wiadomość odpowiada danemu ciągowi bitów, to Twój program powinien ją wypisać.
Jeśli nie ma takich wiadomości lub jest więcej niż jedna, program powinien o tym fakcie poinformować.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia ciągi bitów
odpowiadające kolejnym literom oraz ciągi bitów do zdekodowania,
- dla każdego ciągu stwierdzi, czy da się go jednoznacznie, zdekodować i jeśli tak, to zdekoduje
- wypisze wyniki na standardowe wyjście.
Wejście
W pierwszej linii standardowego wejścia znajduje się liczba
(), oznaczająca liczbę wykorzystywanych liter.
W każdym z kolejnych wierszy znajduje się mała litera alfabetu angielskiego, spacja i odpowiadający tej literze ciąg bitów (cyfr 0 i 1 bez spacji pomiędzy nimi).
Każda litera jest wymieniona co najwyżej raz.
Łączna długość ciągów bitów nie przekracza 150.
W następnym wierszu znajduje się liczba
(), oznaczająca liczbę wiadomości do zdekodowania.
W każdym z następnych wierszy jest jedna wiadomość -
ciąg cyfr 0 i 1 o długości nie większej niż bez rozdzielających spacji.
Wyjście
Twój program powinien wypisać na standardowe wyjście wyniki dekodowania dla kolejnych wiadomości.
Jeśli danemu ciągowi nie odpowiada żadna wiadomość, to należy wypisać w pojedynczym wierszu słowo BLAD, a jeśli więcej niż jedna, to komunikat ZBYT WIELE.
Jeśli natomiast ciągowi odpowiada dokladnie jedna wiadomość, to w jednym wierszu powinno znaleźć się słowo OK, a w następnym - zdekodowana wiadomość.
Przykład
Dla danych wejściowych:
4
k 11111
b 0100
o 01001
r 111111
3
1111101001111011
01010101010101010
111110100111111
poprawną odpowiedzią jest:
OK
kor
BLAD
ZBYT WIELE