Pochylnia
Limit pamięci: 32 MB
Na pochylni na nabrzeżu portowym są ułożone w przypadkowej kolejności beczki w
trzech kolorach: czerwone, zielone i niebieskie. Trzeba je uporządkować, za
pomocą dźwigu w taki sposób, aby na początku (najniżej) były czerwone, następnie
niebieskie, a na końcu (najwyżej) zielone.
Dźwig - w jednym ruchu - może podnieść do góry jednocześnie trzy sąsiednie
beczki w dowolnym miejscu na pochylni i przenieść je na koniec, za beczki leżące
powyżej, które stoczą się pod własnym ciężarem w dół wypełniając lukę.
Trzeba ułożyć plan pracy dźwigu dyktujący w kolejnych ruchach, którą trójkę
beczek przenieść na koniec.
Ułożenie beczek na pochylni zapisujemy za pomocą ciągu liter
, , , gdzie to liczba beczek.
Litery , , w tym ciągu symbolizują
odpowiednio beczkę czerwoną, niebieską lub zieloną. Zakładamy, że liczba beczek
jest nie większa niż oraz, że na pochylni są
przynajmniej beczki zielone.
Plan porządkowania beczek za pomocą dźwigu można zapisać w postaci skończonego
ciągu liczb całkowitych dodatnich nie
większych niż . Kolejny -ty wyraz ciągu to pozycja (licząc od dołu) najniższej z trzech beczek, jakie należy
przenieść na koniec w -tym ruchu.
Przykład
9 beczek ułożonych na pochylni w kolejności: (czerwona, zielona, niebieska,
niebieska, czerwona, niebieska, zielona, zielona, niebieska) zapisujemy za
pomocą ciągu: .
Dźwig pracujący według planu będzie zmieniał ich
ułożenie w następujący sposób: , ,
i po trzech
ruchach uporządkuje je w kolejności czerwone-niebieskie-zielone.
Zadanie
Napisz program, który:
- wczytuje ze standardowego wejścia liczbę beczek , a następnie
ciąg liter , , określający
początkowe ułożenie beczek na pochylni,
- układa plan porządkowania beczek w kolejności czerwone-niebieskie-zielone w
postaci odpowiedniego skończonego ciągu liczb całkowitych dodatnich i zapisuje
ten plan na standardowym wyjściu.
Dla każdego ułożenia początkowego beczek (jeśli są przynajmniej trzy beczki
zielone) istnieje wiele planów ich porządkowania w kolejności czerwone-niebieskie-zielone. Mogą się one różnić liczbą ruchów. Twój program powinien
znaleźć i wypisać tylko jeden z nich. Liczba ruchów nie musi być minimalna, aby
rozwiązanie było poprawne. Powinieneś jednak dążyć do tego by Twój program
układał plany porządkowania beczek w możliwie małej liczbie ruchów i aby
znajdował je możliwie jak najszybciej.
Wejście
- W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba
całkowita nie mniejsza niż i nie większa niż
. Jest to liczba beczek na pochylni.
- W każdym z kolejnych wierszy jest zapisany jeden znak - litera
, albo , określająca kolor odpowiedniej
kolejnej beczki na pochylni. W tym ciągu znaków są przynajmniej 3
litery .
Wyjście
- Na standardowym wyjściu należy zapisać odpowiedni skończony ciąg liczb
całkowitych dodatnich, który jest planem porządkowania ułożenia beczek.
- Każdą liczbę tego ciągu należy zapisać w osobnym wierszu.
Przykład
Dla danych wejściowych:
9
c
z
n
n
c
n
z
z
n
poprawną odpowiedzią jest:
6
2
5
Autor zadania: Andrzej Walat.