Metoda tworzenia haseł opisana w punkcie a) okazała się zawodna, dlatego
Wydział Bezpieczeństwa postanowił zmienić algorytm.
Palindrom to takie słowo, które czytane od lewej do prawej i od
prawej do lewej jest takie same.
Algorytm tworzenia hasła ze słowa w:
- wyznacz najdłuższe słowo x takie, że x jest początkiem słowa w oraz x jest palindromem,
- oznaczmy przez y pozostałą część słowa w, czyli w=xy
- hasło jest równe h=R(y)xy, gdzie R(y) jest odwróconym słowem y.
Przykład:
Słowo --> Maks_Palindrom --> Hasło --------------------------------------------------- KAJAKARSTWO --> KAJAK --> OWTSRAKAJAKARSTWO MAMA --> MAM --> AMAMA KAJAK --> KAJAK --> KAJAK EGZAMIN --> E --> NIMAZGEGZAMIN
Załóżmy, że posortowaliśmy wszystkie hasła w porządku rosnącym. Jakie hasło znajduje się na pozycji drugiej?
Pierwszy wiersz wejścia zawiera liczbę całkowitą z zakresu 2..1000. W każdym z kolejnych n wierszy zapisano jedno słowo, o maksymalnej długości 30 znaków.
Hasło znajdujące się na pozycji drugiej na posortowanej rosnąco liście wszystkich haseł.
Dla danych podanych na wejściu:
10 SSYLETYRYFOAFYGLBZLKBD IZKYTCWOXTGUYHIISZATTISF PAZNTPQEXOJZXUGNLCHBVTG DIEQDNRPVVJV ZGXDREXIQMGTPZKYGGWOVWXRUQOC CHLZY ZG DAKSQNAEWVRTEBJZKDPGAUW XWHOWDRRBAIZTARG TOIODJNGDYNIRBJPCSI
Poprawną odpowiedzią jest wyjście:
DBKLZBLGYFAOFYRYTELYSSYLETYRYFOAFYGLBZLKBD
Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5
Opcje zadania:
Biblioteki : iostream iomanip cmath string Limit czasu : 0.1 s Limit pamięci : 32 MB Słowa niedozwolone :