Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_17_07 - HANOI

hanoi

Kolejną sesję z algorytmiki studenci profesora Algobita mają już za sobą, niestety nie wszyscy. Niektórzy jeszcze raz będą musieli spotkać się z profesorem we wrześniu, no i jest Jasiu, którego historia jest następująca. Gdy wszedł na egzamin, profesor Algobit właśnie analizował ustawienie krążków wież Hanoi. Gdy zobaczył swojego ulubionego studenta  zaproponował mu układ. Powiedział, że jeśli Jasiu znajdzie sposób na określenie liczby ruchów, jakie trzeba wykonać aby otrzymać dane ustawienie krążków na trzech drążkach, to postawi mu najwyższą ocenę. Pomóż młodemu studentowi i rozwiąż ten problem.

Polega on na wypisaniu, po ilu ruchach optymalnego przestawiania krążków wież Hanoi otrzymamy dane ich ustawienie.

Wejście

W pierwszym wierszu jedna liczba k określająca liczbę krążków (0<k<21).

Następnie jedna liczba q oznaczająca liczbę zapytań (q<100000).

Każde zapytanie składa się z trzech wierszy oznaczających odpowiednio ustawienie krążków na pierwszym, drugim oraz trzecim słupku w następującym formacie:

najpierw jedna liczba n określająca liczbę krążków, następnie malejący ciąg n wielkich liter należących do przedziału [A..T].

Wyjście

Dla każdego zapytania jedna liczba określająca numer przestawienia krążków, które przedstawia zapytanie. Położenie pierwotne ma wartość 0.

Przykład

Wejście:
4
1
0
3 C B A
1 D
Wyjście:
8
Uwaga! Krążek pod numerem A ma najmniejszą średnicę oraz A < B < C < ... < T.

Dodane przez:Marcin Kasprowicz
Data dodania:2014-07-01
Limit czasu wykonania programu:1s-1.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

ukryj komentarze
2014-07-23 18:36:34 Witold D³ugosz
Położenie pierwotne - tak, wszystkie krążki na pierwszym słupku.
Położenie końcowe - bez znaczenia. Trzeba obliczyć liczbę ruchów potrzebnych do uzyskania podanego ustawienia.
2014-07-23 18:12:22 Bart³omiej Koby³ecki
Polożenie pierwotne ma wszystkie krążki na pierwszym słupku? Położenie końcowe ma wszystkie krążki na trzecim słupku?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.