Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_17_06 - Spadające słówka

Spadające słówka

Spadające słówka to łamigłówka w formie diagramu o trzech wierszach i kilkunastu kolumnach. Początkowo diagram uzupełniony jest literami i znakiem _ oznaczającym spację. Łamigłówka polega na zamianie komórek parami w obrębie kolumny tak, aby w każdym wierszu powstały wyłącznie słowa z dostępnego słownika. Zadanie polega na napisaniu programu, który będzie rozwiązywał tak zdefiniowaną łamigłówkę.

Pisząc program należy założyć, ze każda podana na wejściu łamigłówka jest rozwiązywalna oraz dla każdej łamigłówki dostępny jest słownik złożony z 43583 słów. Ponadto kazdy wiersz rozpoczyna się literą i w każdym wierszu występuje co najmniej jedno ukryte słowo, a w przypadku dwóch lub więcej słów w wierszu, rozdzielone są one pojedynczym znakiem spacji _.

Wejście
Pierwszy wiersz wejścia zawiera liczbę wyrazów w słowniku i jest ona stała. Drugi wiersz zawiera 43583 słów ze słownika, który można pobrać wyżej.
Trzeci wiersz to liczba przypadków testowych d (1 ≤ d ≤ 20) do rozpatrzenia. Dalej opisane są przypadki testowe. Każdy przypadek to cztery wiersze. W pierwszym wierszu podana jest liczba n (10 ≤ n ≤ 20) oznaczająca liczbę kolumn diagramu. Kolejne trzy wiersze opisują diagram, na które składają się ciągi długości n złożone z małych liter i znaku _ oznaczającego spację.

Wyjście
Dla każdej łamigłówki należy wypisać trzy wiersze przedstawiające rozwiązany diagram. Ponieważ łamigłówki mogą posiadać wiele rozwiązań, należy znaleźć takie, którego porządek leksykograficzny ciągów w wierszach (od góry do dołu) będzie najmniejszy. Między przypadkami testowymi dozwolony jest dodatkowy znak końca linii.

Przykład

Wejście

43583
abak abaka abakan abakus ...
2
10
kajkz_s___
fonduo____
barnyr____
13
koto_ktokoat_
kttekokotkow_
koo_k_t__kt_a

Wyjście

bardzo____
fajny_____
konkurs___

kotek_kotka__
koto_kto_kot_
kto_kot_kotwa

Dodane przez:Mariusz Śliwiński
Data dodania:2014-07-01
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

ukryj komentarze
2014-07-12 19:21:24 Mateusz Wasylkiewicz
Co dokładnie oznacza "porządek leksykograficzny od góry do dołu"? Czy w porządku tym mają znaczenie spacje? Jeśli tak, to czy są większe, czy mniejsze od liter?
2014-07-12 17:54:39 Mariusz ¦liwiñski
Nie, nie ma takich przypadków.
2014-07-12 17:51:15 Mateusz Wasylkiewicz
Czy w rozwiązaniu, wiersze mogą zaczynać się znakami spacji?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.