Polish version    English version  
  O olimpiadzie -> Zadania -> II OI 1994/1995


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
II Olimpiada Informatyczna 1994/95

Zadanie: POC
Autor: Andrzej Walat
Pochylnia

Zawody III stopnia  
Plik źródłowy: POC.??? (np. pas, c, cpp)
Plik wykonywalny: POC.exe
Plik wejściowy: POC.in
Plik wyjściowy: POC.out

 

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 l liter c, n, z, gdzie l to liczba beczek. Litery c, n, z w tym ciągu symbolizują odpowiednio beczkę czerwoną, niebieską lub zieloną. Zakładamy, że liczba beczek l jest nie większa niż 2000 oraz, że na pochylni są przynajmniej 3 beczki zielone.

Plan porządkowania beczek za pomocą dźwigu można zapisać w postaci skończonego ciągu R = (r1,...,rk) liczb całkowitych dodatnich nie większych niż l- 2. Kolejny i-ty wyraz ciągu R - ri to pozycja (licząc od dołu) najniższej z trzech beczek, jakie należy przenieść na koniec w i-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: (c, z, n, n, c, n, z, z, n).

Dźwig pracujący według planu R = (6, 2, 5) będzie zmieniał ich ułożenie w następujący sposób: (c, z, n, n, c, n, n, z, z), (c, c, n, n, z, z, z, n, n), (c, c, n, n, n, n, z, z, z) i po trzech ruchach uporządkuje je w kolejności czerwone- niebieskie-zielone.

Zadanie

Napisz program, który:
  • wczytuje z pliku tekstowego POC.IN liczbę beczek l, a następnie ciąg l liter c, n, z 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 w pliku tekstowym POC.OUT.

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 pliku tekstowego POC.IN jest zapisana jedna liczba całkowita l nie mniejsza niż 3 i nie większa niż 2000. Jest to liczba beczek na pochylni.
  • W każdym z kolejnych l wierszy jest zapisany jeden znak - litera c, n, albo z, określająca kolor odpowiedniej kolejnej beczki na pochylni. W tym ciągu l znaków są przynajmniej 3 litery z.

Wyjście

  • W pliku tekstowym POC.OUT 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 pliku POC.IN:
9
c
z
n
n
c
n
z
z
n

poprawnym rozwiązaniem jest następujący ciąg w pliku POC.OUT:
6
2
5

Twój program powinien szukać pliku POC.IN w katalogu bieżącym i tworzyć plik POC.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę POC.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonywalnej powinien być zapisany w pliku POC.EXE.




Wersja do druku