In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Bajtocki Instytut Telekomunikacyjny (BIT) zajmuje się ustalaniem standardów przesyłania danych w sieciach telekomunikacyjnych Bajtocji. Bajtazar, jeden z informatyków pracujących w BIT, zajmuje się kodami prefiksowymi - specjalnym sposobem reprezentowania znaków. Każdemu znakowi bajtockiego alfabetu odpowiada pewien ciąg bitów, nazywany kodem tego znaku. Kody znaków mają następujące własności:
znak | kod znaku |
A | 00 |
B | 10 |
C | 11 |
D | 010 |
E | 011 |
Kodowanie ciągu znaków za pomocą kodu prefiksowego polega na połączeniu kodów jego kolejnych znaków. Na przykład zakodowany ciąg BACAEBABAE ma postać 1000110001110001000011.
Bajtazar zauważył, że jeśli pewna liczba początkowych bitów zostanie utracona, to zakodowana informacja może być odkodowana niepoprawnie albo wcale. Na przykład, jeśli usuniemy pięć pierwszych bitów z ciągu podanego powyżej, to powstały ciąg 10001110001000011 zostanie odkodowany jako BACBABAE. Pięć ostatnich liter (BABAE) jest poprawnych, jednak trzy pierwsze (BAC) nie. Bajtazar zauważył, że wszystkie litery po pierwszym E zostały odkodowane poprawnie. Doszedł do wniosku, że zawsze, jeśli żadne bity kodu E nie zostaną utracone, to wszystkie kolejne znaki za E zostaną odkodowane poprawnie. Tak będzie dla dowolnego kodowanego ciągu znaków, w którym występuje E. Zauważył on też, że litera D też ma tę własność, ale litery A, B i C tej własności nie mają.
Opisaną własność kodów znaków E i D Bajtazar określił jako bycie kodem synchronizującym. Bajtazar powierzył Ci zadanie napisania programu znajdującego, dla danego kodu prefiksowego, wszystkich kodów synchronizujących. Aby zaoszczędzić czas, wymyślił sobie, że pokaże Ci wszystkie kody znaków na swoim binarnym monitorze. Monitor ma cztery przyciski:
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę przycisków naciśniętych przez Bajtazara. W kolejnym wierszu znajduje się -literowy napis złożony ze znaków '0', '1', 'B' oraz 'X', oznaczających poszczególne przyciski. Każde naciśnięcie przycisku X oznacza kolejny znak (znaki numerujemy od 1). Suma długości wszystkich kodów nie przekroczy .
W pierwszym wierszu standardowego wyjścia należy wypisać liczbę - liczbę kodów synchronizujących. W kolejnych wierszach należy wypisać, w porządku rosnącym, numery znaków, które są kodami synchronizującymi, po jednym w wierszu. Jeżeli dla danego kodu prefiksowego nie ma żadnych kodów synchronizujących, to należy wypisać tylko jeden wiersz zawierający liczbę 0.
Dla danych wejściowych:
21 11XB0XBB00XB11XB0XBBB
poprawną odpowiedzią jest:
2 4 5
Oto kolejne kody, które pojawiają się na monitorze Bajtazara: 11, 10, 00, 011, 010. Kody 011 i 010 są kodami synchronizującymi.
Autor zadania: Marek Biskup.