 |
| Aktualności |
| O olimpiadzie |
| Komitety |
| XVIII OI 2010/2011 |
| Historia OI |
| Książeczki OI |
| Reprezentacja |
| Obozy Olimpiady |
| Galeria zdjęć |
| Ciekawe odsyłacze |
| OIG LiveCD |
| IV OIG 2009/2010 |
| Historia OIG |
| SIO |
| MAIN |
Przekład: Krzysztof Diks, Andrzej Walat
iShongololo to zuluska nazwa krocionoga. Jest to długi, błyszczący, czarny owad, mający wiele nóg.
![[ Żarłoczne iShongololo ]](../kacik/isho.gif)
iShongololo żywi się jadalnymi "owocami". Na potrzeby tego zadania przyjmujemy, że mają one kształt prostopadłościanów o całkowitoliczbowych rozmiarach L (length - długość), W (width - szerokość) i H (height - wysokość), i są podzielone na bloki o rozmiarze 1x1x1. Poszczególne bloki będziemy oznaczać (a,b,c), gdzie 1<=a<=L, 1<=b<=W, 1<=c<=H.
Zadanie
Twoim zadaniem będzie podanie jak najdłuższego planu trasy dla iShongololo bez naruszenia ustalonych ograniczeń. Na początku iShongololo znajduje się na zewnątrz owocu. Pierwszym blokiem, którego zawartość musi zjeść jest (1, 1, 1). Następnie musi wejść do tego bloku. iShongololo kończy, gdy nie może już zgodnie z regułami zjeść żadnego bloku, ani wykonać ruchu.Ograniczenia
- iShongololo zajmuje dokładnie jeden pusty blok.
- iShongololo zjada na raz jeden pełny blok.
- iShongololo nie może wykonać ruchu na pozycję, na której już był (tzn. zawrócić lub przeciąć swoją ścieżkę).
- iShongololo nie może wejść do pełnego (nie zjedzonego) bloku lub wyjść na zewnątrz owocu.
- iShongololo może wykonać ruch tylko do bloku o przyległej ścianie; może też zjeść blok o przyłeglej ścianie, ale tylko taki, który nie ma wspólnej ściany z żadnym innym pustym blokiem.
Dane
Przygotowaliśmy cztery zestawy danych:
| Zestaw | L | W | H |
|---|---|---|---|
| Zestaw nr 0 | 4 | 3 | 2 |
| Zestaw nr 1 | 3 | 3 | 10 |
| Zestaw nr 2 | 40 | 40 | 40 |
| Zestaw nr 3 | 39 | 57 | 44 |
Plan trasy iShongololo
Pierszy wiersz opisu powinien zawierać pojedyńczą liczbę całkowitą oznaczającą numer zestawu. W każdym z kolejnych wierszy powinna być zapisana komenda dla iShongololo. Komendy mogą mieć następującą postać:
- E L W H - zjedz blok o współrzędnych (L, W, H)
- M L W H - przejdź do bloku o współrzędnych (L, W, H)
Oto przykład poprawnego opisu trasy iShongololo dla zestawu o numerze 0.
0 E 1 1 1 M 1 1 1 E 2 1 1 E 1 1 2 E 1 2 1 M 1 2 1 E 1 3 1 M 1 3 1 E 2 3 1 E 1 3 2 M 1 3 2
Miarą oceny planu jest liczba jego instrukcji, jednak w przypadku wystąpienia nieprawidłowych komend (np. niezgodnych z ograniczeniami) taki plan jest odrzucany
Wersja do druku