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.
Sieć trójkątów jest zbudowana z równobocznych trójkątów o boku 1. Ścieżką na sieci trójkątów nazywamy dowolny skończony ciąg trójkątów (o boku 1) sieci, taki, że każde kolejne dwa trójkąty w tym ciągu mają wspólny bok.
Figurę utworzoną przez punkty skończonej liczby trójkątów sieci nazywamy wyspą, jeśli dowolne dwa zawarte w niej trójkąty sieci można połączyć ścieżką utworzoną z trójkątów zawartych w tej figurze.
Figury przedstawione na rysunkach 1.1, 1.2 i 1.3 są wyspami. Figura na rysunku 1.4 nie jest wyspą. Figury na rysunkach 2.2, 2.3 i 2.5 są przystające.
Zamierzamy dla każdego opisać w systematyczny sposób wszystkie nieprzystające wyspy, jakie można utworzyć z trójkątów o boku 1, i policzyć, ile ich jest.
Brzeg każdej wyspy, zbudowanej z co najwyżej dziesięciu trójkątów, jest łamaną zamkniętą złożoną z jednostkowych odcinków siatki i można go obiec (obrysować bez odrywania ołówka od papieru) w ten sposób, że dokładnie raz przebiegamy każdy odcinek brzegu i wracamy do punktu wyjścia. Może się zdarzyć, że trzeba będzie przy tym przejechać więcej niż raz przez ten sam punkt (patrz rysunek 2.4).
W przypadku wysp zbudowanych z co najwyżej dziesięciu trójkątów nie jest możliwa sytuacja taka, jak na rysunku 1.2, że brzeg figury składa się z dwóch rozłącznych części i nie można go obiec (obrysować bez odrywania ołówka od papieru).
Obiegając brzeg, po każdym jednostkowym odcinku wykonujemy skręt jednego z następujących typów:
Słowa cdddcddd, dcdddcdd, cbbbcbbb opisują różne obiegi figury na rysunku 2.1.
Słowa cbeddcde, adcabcbb, abcbbadc opisują różne obiegi figury na rysunku 2.2.
Słowa acdabbcb i cddebced opisują różne obiegi figury na rysunku 2.3.
Jeśli obiegając brzeg wyspy mamy stale jej wnętrze po prawej stronie, to mówimy, że jest to obieg prawoskrętny.
Dla każdej wyspy można wyznaczyć zbiór wszystkich wysp do niej przystających oraz ich obiegi prawoskrętne. Kodem wyspy nazwiemy słowo, które:
Dla wysp przedstawionych na rysunkach 2.2 i 2.3, które są przystające, bierzemy pod uwagę wszystkie prawoskrętne obiegi obydwu:
beddcdec, eddcdecb, ddcdecbe, dcdecbed, cdecbedd, decbeddc, ecbeddcd, cbeddcde
oraz
bcedcdde, cedcddeb, edcddebc, dcddebce, cddebced, ddebcedc, debcedcd, ebcedcdd
i jako kod każdej z nich bierzemy to słowo, które w porządku alfabetycznym należy umieścić na pierwszym miejscu: bcedcdde.
Kodem wyspy przedstawionej na rysunku 2.4 jest słowo: aadecddcddde.
Napisz program, który:
W pierwszym wierszu standardowego wejścia podana jest liczba całkowita (), oznaczająca liczbę zapytań. Każdy z kolejnych wierszy zawiera opis zapytania pewnego typu. Zapytanie typu 1 składa się z litery K oraz kodu wyspy składającej się z co najwyżej dziewięciu trójkątów, oddzielonych pojedynczym odstępem. Zapytanie typu 2 składa się z litery N oraz liczby całkowitej (), oddzielonych pojedynczym odstępem.
Na standardowe wyjście wypisz odpowiedzi dla poszczególnych zapytań.
Dla zapytań typu 1 należy najpierw wypisać liczbę różnych kodów wysp, które można utworzyć z przystających wysp opisanych podanym kodem poprzez dodanie jednego trójkąta. W następnym wierszu należy wypisać wszystkie te kody w kolejności alfabetycznej, pooddzielane pojedynczymi odstępami.
Dla zapytań typu 2 należy wypisać liczbę różnych kodów wysp utworzonych z trójkątów. W kolejnym wierszu należy wypisać wszystkie te kody w kolejności alfabetycznej.
Dla danych wejściowych:
2 K adeccecced N 5
poprawną odpowiedzią jest:
5 acedccecced addebcecced adebebecced adecbedcced cceccecce 4 aedddde bdecdde bececde ccedcde
Autor zadania: Andrzej Walat (zadanie z I Olimpiady Informatycznej).