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



: konkurs -> archiwum -> 2005 -> zadania
konkurs -> Kolędnicy misyjni 2012/2013 Propozycja Występują: Anioł (gra na instrumencie), Gwiazdor z gwiazdą misyjną, Maryja z Dzieciątkiem, 6 dzieci
konkurs -> V konkurs muzyczno-literacki w zakresie gry a vista I czytania prozy I poezji
konkurs -> Matematyczno przyrodnicze zmagania na renesansową nutę”, czyli obchody Dnia Patrona, Przedmiotów Ścisłych oraz Dnia Ziemi
konkurs -> Zakres tematyczny na konkurs „Bitwy I broń II wojny światowej 1939 – 1945 ”
konkurs -> Przykładowe zadania na konkurs „Euklides”
konkurs -> Konkurs na najlepszy placek drożDŻowy pikniku „leszczyńskie smaki” 2013
konkurs -> Konkursy w pracy szkoły zestawienie bibliograficzne w wyborze za lata 2000-2006 w oparciu o zbiory Biblioteki Pedagogicznej w Ostrołęce Filia w Przasnyszu Konkursy czytelnicze
konkurs -> Nagrody stowarzyszenia dziennikarzy polskich
konkurs -> Wyniki I etapu




©absta.pl 2019
wyślij wiadomość

    Strona główna