Gra
Limit pamięci: 32 MB
Plansza do gry składa się z
kolejno ponumerowanych pól.
Na planszy znajduje się
czarnych pionków i
białych.
Czarne pionki są rozmieszczone na
początkowych polach planszy (na polach o numerach
od 1 do
), natomiast białe na
końcowych polach (na polach o numerach od
do
).
Pole o numerze
jest początkowo wolne.
![](images/PA2006/rysunek.png)
a. początkowe ustawienie pionków na planszy dla
i możliwe ruchy,
b. plansza po wykonaniu ruchu pionkiem z pola 5 i możliwe ruchy
Na planszy można wykonywać dwa rodzaje ruchów polegających na przesunięciu pionka na sąsiednie wolne pole,
albo na przeskoczeniu pionkiem nad sąsiednim pionkiem odmiennego koloru i wylądowaniu na wolnym polu.
Celem gry jest zamiana miejscami pionków czarnych i białych (tzn. rozmieszczenie czarnych pionków
na polach o numerach od
do
, a białych na polach o numerach od 1 do
).
Interesuje nas najkrótszy ciąg dozwolonych wyników wystarczających do zreazlizowania tego celu.
Zadanie
Napisz program, który:
-
wczyta liczbę
oznaczającą liczbę czarnych pionków na planszy,
-
wyznaczy najkrótszy ciąg ruchów realizującą cel gry,
-
wypisze wynik.
Wejście
W jedynym wierszu wejścia znajduje się liczba całkowita
(
).
Wyjście
W pierwszym wierszu wyjścia należy wypisać liczbę
![](images/PA2006/gra-tex.17.png)
oznaczająca minimalną liczbę ruchów wystarczających do tego,
aby doprowadzić pionki na planszy do konfiguracji końcowej. W kolejnych
![](images/PA2006/gra-tex.18.png)
wierszach należy zapisać po jednej liczbie
z przedziału
![](images/PA2006/gra-tex.19.png)
.
Liczba znajdująca się w
![](images/PA2006/gra-tex.20.png)
-szym wierszu (dla
![](images/PA2006/gra-tex.21.png)
) oznacza
numer pola, z którego należy przesunąć pionek w
![](images/PA2006/gra-tex.22.png)
-tym ruchu.
Jeśli istnieje więcej niż jedno rozwiązanie, Twój program może wypisać dowolne z nich.
Przykład
Dla danych wejściowych:
1
poprawną odpowiedzią jest:
3
1
3
2
Autor zadania: Tomasz Idziaszek.