In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.
Napisz program który:
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.
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.
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ń.