<Wyślij rozwiązanie> [
0/100]
Statystyki zadaniaLiczba osob: 29
Liczba osob na 100 punktow: 13
Sredni wynik: 69.2414
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
<Wyślij rozwiązanie> [
0/100]