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.
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:
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!
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.
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).
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.