Okresowość
Limit pamięci: 32 MB
Bajtazar, król Bitocji, zarządził reformę nazwisk swoich poddanych.
Nazwiska mieszkańców Bitocji często zawierają powtarzające się frazy,
np. w nazwisku Abiabuabiab dwukrotnie występuje fragment abiab.
Bajtazar chce zamienić nazwiska swoich poddanych na ciągi bitów takiej samej długości
jak ich oryginalne nazwiska.
Chciałby przy tym w jakimś stopniu zachować sposób, w jaki w oryginalnych nazwiskach powtarzają
się te same frazy.
W dalszej części zadania, dla prostoty, będziemy utożsamiać wielkie i małe litery w nazwiskach.
Dla dowolnego ciągu znaków (liter lub bitów) powiemy, że liczba
naturalna () jest okresem , jeżeli dla wszystkich .
Przez będziemy oznaczać zbiór wszystkich okresów .
Na przykład, ,
oraz .
Bajtazar zdecydował, że każde nazwisko ma zostać zamienione na ciąg bitów:
-
tej samej długości co oryginalne nazwisko,
-
o dokładnie takim samym zbiorze okresów co oryginalne nazwisko,
-
ma to być najmniejszy (w porządku leksykograficznym1)
ciąg bitów spełniający powyższe warunki.
Na przykład, nazwisko
ABIABUABIAB powinno zostać zamienione na
01001101001,
BABBAB na
010010, a
BABURBAB na
01000010.
Bajtazar poprosił Cię o napisanie programu, który pomógłby w tłumaczeniu dotychczasowych nazwisk
jego poddanych na nowe.
W nagrodę będziesz mógł zachować swoje oryginalne nazwisko!
Wejście
W pierwszym wejściu standardowego wejścia znajduje się jedna liczba całkowita
- liczba nazwisk do przetworzenia ().
Nazwiska są podane w kolejnych wierszach, po jednym w wierszu.
Każde z nazwisk składa się z od do wielkich liter (alfabetu angielskiego).
W testach wartych łącznie 30% punktów każde nazwisko składa się z co najwyżej liter.
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy.
W kolejnych wierszach powinny znajdować się ciągi zer i jedynek (niezawierające odstępów)
odpowiadające kolejnym nazwiskom z wejścia.
W przypadku, gdy dla danego nazwiska nie istnieje
ciąg bitów zgodny z warunkami zadania, należy dla tego nazwiska wypisać "XXX" (bez cudzysłowów).
Przykład
Dla danych wejściowych:
3
ABIABUABIAB
BABBAB
BABURBAB
poprawną odpowiedzią jest:
01001101001
010010
01000010
1 Ciąg bitów jest mniejszy w porządku leksykograficznym od ciągu bitów
, jeżeli dla pewnego , , mamy oraz dla wszystkich
mamy .
Autor zadania: Wojciech Rytter.