Labirynt

Limit pamięci: 128 MB

Uwaga: W trakcie zawodów możesz poznać wynik punktowy trzech wybranych zgłoszeń do tego zadania.

Bajtazar przeczytał niedawno ciekawą historię. Jej bohaterem był jakiś grecki królewicz, który pokonał straszliwego potwora za pomocą kłębka wełny, lub coś w tym rodzaju. Ale to nie to tak zafascynowało Bajtazara. Najbardziej spodobało mu się, że kluczowe wydarzenia działy się w labiryncie. Od tej pory Bajtazar ma bzika na punkcie labiryntów.

Bajtazar rysuje plany labiryntów na kratkowanej kartce papieru. Każdy taki plan jest wielokątem, którego boki (reprezentujące ściany labiryntu) są równoległe do brzegów kartki (tj. osi prostokątnego układu współrzędnych) i każde dwa kolejne boki są do siebie prostopadłe. Bajtazar zauważył, że jeśli na jednej ze ścian takiego labiryntu umieścimy wejście, a następnie wejdziemy do niego i, idąc, cały czas będziemy trzymać się prawą ręką ściany, to na pewno obejdziemy cały labirynt, wracając na końcu z powrotem do wejścia.

Co więcej, podczas takiego obejścia możemy notować wykonywane przez nas zakręty. Zapisujemy literę L, jeśli podczas przechodzenia na kolejną ścianę obracamy się w lewo, zaś P, jeśli obracamy się w prawo. Bajtazar zastanawia się, dla jakich słów złożonych z liter L i P istnieje labirynt, który spowoduje, że zanotujemy takie słowo podczas obchodzenia tego labiryntu.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedno -literowe słowo () złożone z liter L i P, które opisuje ciąg kolejnych zakrętów napotykanych podczas obchodzenia labiryntu.

W testach wartych 50% punktów zachodzi dodatkowy warunek .

Wyjście

Jeśli nie da się skonstruować labiryntu według opisu z wejścia, na standardowym wyjściu należy wypisać słowo NIE. W przeciwnym wypadku na wyjście należy wypisać dokładnie wierszy zawierających opis przykładowego labiryntu. W -tym z nich powinny znaleźć się dwie liczby całkowite i () oddzielone pojedynczym odstępem, oznaczające współrzędne -tego wierzchołka na planie labiryntu. Wierzchołki powinny zostać wypisane zgodnie z kolejnością ich występowania na obwodzie wielokąta, przeciwnie do ruchu wskazówek zegara; można zacząć od dowolnego wierzchołka i nie trzeba zaznaczać umiejscowienia drzwi.

Przykład

Dla danych wejściowych:

LLLLPPLL

poprawną odpowiedzią jest:

0 0
2 0
2 2
-1 2
-1 -2
1 -2
1 -1
0 -1

Testy "ocen":

• 1ocen: , słowo LLLLLLLLLLLL, odpowiedź NIE;
• 2ocen: , spirala zakręcająca w lewo;
• 3ocen: , schodki.

Wizualizator wyjść

Do tego zadania dołączony jest wizualizator wyjść, który dla pliku zgodnego z formatem wyjścia rysuje odpowiadający mu labirynt. Aby go uruchomić, wypakuj to archiwum i wykonaj komendę:

./labwiz

Dla plików, które nie zawierają opisu labiryntu zgodnego z formatem wyjścia, zachowanie wizualizatora jest nieokreślone.

Autor zadania: Tomasz Idziaszek