English
Zadanie Gra (gra)
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.
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ę
oznaczająca minimalną liczbę ruchów wystarczających do tego,
aby doprowadzić pionki na planszy do konfiguracji końcowej. W kolejnych 
wierszach należy zapisać po jednej liczbie
z przedziału 
.
Liczba znajdująca się w 
-szym wierszu (dla 
) oznacza
numer pola, z którego należy przesunąć pionek w 
-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:1poprawną odpowiedzią jest:
3 1 3 2
Autor zadania: Tomasz Idziaszek.