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ń.