Błękitno-czerwone



Pobieranie 8.97 Kb.
Data04.05.2016
Rozmiar8.97 Kb.

WEiTI Kwalifikacje na AMPPZ / CEPC, 15 października 2005

Zadanie A

Błękitno-czerwone Wieże Hanoi
Firma CellTik, zajmująca się produkcją gier do telefonów komórkowych, postanowiła wprowadzić na rynek nieco zmodyfikowaną klasyczną grę-łamigłówkę Wieże Hanoi. Jak wiadomo, w oryginalnej łamigłówce mamy 3 kołki ("wieże") oznaczone literami A, B, C oraz n krążków o malejących średnicach nanizanych na kołek A; zadanie polega na przeniesieniu w minimalnej liczbie ruchów krążków z kołka A na kołek B wykorzystując kołek C jako miejsce pomocnicze i przy zachowaniu reguł:

  1. w jednym ruchu można przenieść jeden krążek pomiędzy wieżami

  2. nigdy krążek większy nie spoczywa na mniejszym.

Planowana modyfikacja gry, przy zachowaniu powyższych reguł, sprowadza się do następujących nowości:



  • krążki mogą być kolorowe, błękitne lub czerwone

  • konfiguracją początkową gry może być dowolne rozmieszczenie krążków na wszystkich 3 wieżach spełniające warunek 2. powyżej

  • konfiguracją końcową jest stan, w którym wszystkie krążki błękitne znajdują się na kołku B a wszystkie krążki czerwone na kołku C (kołek A jest wolny).

Wszystkie szczegóły związane z prezentacją graficzną i interakcją (takie jak: określenie liczby krążków, losowanie lub określanie kolorów, generowanie lub ustawianie konfiguracji początkowej, obsługa historii konfiguracji początkowych, rejestracja najlepszych wyników dla konfiguracji rejestrowanych w historii) zostały już w projekcie gry domknięte. Pozostaje do uzupełnienia stosunkowo prosta funkcja: wyznaczenie dla aktualnej konfiguracji minimalnej liczby ruchów potrzebnych do ukończenia gry. Twoim zadaniem jest napisanie programu realizującego takie obliczenia.
Wejście

Standardowy strumień wejściowy składa się z ciągu wierszy tekstu. W pierwszym wierszu znajduje się liczba całkowita k określająca liczbę konfiguracji początkowych do sprawdzenia. W następnych k wierszach definiowane są poszczególne konfiguracje początkowe kodowane przy pomocy łańcuchów liter postaci xnxn-1...x2x1 gdzie xj  {A, a, B, b, C, c} i oznacza, że krążek o średnicy j jest umieszczony odpowiednio na wieży A, B, albo C; duża litera implikuje kolor błękitny, mała litera - kolor czerwony. Na przykład ciąg znaków AaBac oznacza, że jest 5 krążków o umownych średnicach od 1 do 5, na wieży A znajdują się krążki 5 4 2, na wieży B krążek 3 i na wieży C krążek 1; krążki 5, 3 są błękitne, pozostałe czerwone. Maksymalna liczba krążków nie przekracza 30.


Wyjście

Dla każdej konfiguracji wejściowej program wyprowadza do standardowego strumienia wyjściowego 1 wiersz zawierający minimalną liczbę ruchów potrzebnych do osiągnięcia konfiguracji końcowej.


Przykład:

Wejście

3

AA

Cba

AbbC

Wyjście

3

6

8




©absta.pl 2016
wyślij wiadomość

    Strona główna