Tetris Attack
Limit pamięci: 32 MB
Ostatnimi czasy w Bajtocji bardzo popularną grą stała się
łamigłówka "Tetris attack".
Jej uproszczona wersja ma następującą postać:
Gracz otrzymuje do dyspozycji stos, na którym umieszczono
elementów (jeden na drugim), oznaczonych
różnymi symbolami.
Przy tym każdym symbolem są oznaczone dokładnie dwa elementy na
stosie.
Ruch gracza polega na zamianie dwóch sąsiednich elementów
miejscami.
Jeśli w wyniku zamiany na stosie sąsiadują ze sobą elementy
oznaczone identycznymi symbolami, to w "magiczny" sposób znikają,
a elementy znajdujące się powyżej spadają w dół (być może powodując
kolejne zniknięcia).
Celem gracza jest opróżnienie stosu w jak najmniejszej liczbie ruchów.
Zadanie
Napisz program który:
- wczyta ze standardowego wejścia opis początkowej zawartości stosu,
- obliczy rozwiązanie wymagające minimalnej liczby ruchów,
- wypisze znalezione rozwiązanie na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna
liczba całkowita ,
.
W kolejnych
wierszach zapisana jest początkowa zawartość stosu.
Wiersz
-wszy zawiera jedną liczbę całkowitą
-
symbol elementu znajdującego się na wysokości
(
).
Każdy symbol występuje na stosie dokładnie 2 razy.
Na początku żadne dwa identyczne symbole nie występują
obok siebie. Ponadto dane testowe są tak dobrane, że istnieje
rozwiązanie zawierające nie więcej niż
ruchów.
Wyjście
Na standardowym wyjściu należy wypisać opis rozwiązania,
wymagającego minimalnej liczby ruchów.
Pierwszy wiersz powinien zawierać jedną liczbę całkowitą -
długość najkrótszego rozwiązania.
Kolejne
wierszy powinno zawierać opis rozwiązania, czyli ciąg
liczb całkowitych
, po jednej w każdym wierszu.
Wartość
oznacza, że w
-tym ruchu gracz zdecydował o
zamianie elementów, znajdujących się na wysokościach
oraz
.
Jeżeli istnieje wiele rozwiązań, to Twój program powinien wypisać dowolne z nich.
Przykład
Dla danych wejściowych:
5 5 2 3 1 4 1 4 3 5 2
poprawną odpowiedzią jest:
2 5 2
natomiast dla danych wejściowych:
3 1 2 3 1 2 3
poprawnym wynikiem jest:
3 3 4 2
jak również:
3 4 3 2
Autor zadania: Tomasz Waleń.