Drzewo i mrówki
Limit pamięci: 6 MB
Informatycy lubią drzewa. Mrówki także lubią drzewa.
Niech więc będzie dane drzewo, po którym chodzą dwie mrówki -
Lewa Mrówka i Prawa Mrówka - w sposób pokazany na powyższym rysunku (po ścieżce
oznaczonej kropkowaną linią). Rozpoczynają one swoją wędrówkę na początku pnia,
po przeciwnych jego stronach.
Lewa Mrówka pokonuje każdą krawędź drzewa w czasie dwóch sekund, idąc od korzenia (w górę),
a w czasie jednej sekundy, idąc w kierunku korzenia (w dół).
Prawa Mrówka jest od niej dwa razy
szybsza. W momencie, gdy mrówki spotykają się, obydwie zawracają. Jeśli
któraś z nich zejdzie z drzewa na ziemię, natychmiast zaczyna wchodzić
na drugą stronę pnia. Poza tym mrówki są tak malutkie, że nawet mikroskop
nie wystarczyłby do ich zobaczenia (na rysunku celowo zostały powiększone).
Twoim zadaniem jest napisanie programu, który obliczy, po jakim czasie mrówki zawrócą po raz drugi.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita
() oznaczająca liczbę zestawów testowych opisanych
w dalszej części wejścia.
Opis każdego zestawu składa się z dwóch wierszy.
W pierwszym z nich znajduje się parzysta liczba () oznaczająca liczbę krawędzi drzewa. W drugim
wierszu znajduje się opis drzewa. Jest to napis długości
reprezentujący liczbę binarną -bitową zapisaną w systemie szesnastkowym
(przy użyciu cyfr oraz małych liter od a do f).
Liczba ta opisuje, jak wygląda obejście całego drzewa przez Lewą Mrówkę przy założeniu, że Prawa Mrówka stoi w miejscu.
Kolejne bity tej liczby (od lewej) oznaczają, czy idąc
po kolejnych krawędziach na swojej ścieżce, Lewa Mrówka oddala się od korzenia (bit
1), czy też zbliża się do korzenia (bit 0). Drzewo posiada pień, tzn. dokładnie
jedna krawędź wychodzi z korzenia drzewa.
Rozmiar żadnego pliku wejściowego nie przekroczy 50 MB.
Uwaga: to jest istotnie więcej niż rozmiar pamięci dostępnej dla Twojego programu.
Wyjście
Twój program powinien wypisać wierszy
z odpowiedziami dla kolejnych zestawów testowych.
Odpowiedzią dla zestawu jest
czas w sekundach, po którym mrówki zawrócą po raz drugi, wypisany jako nieskracalny ułamek
p/q (bez spacji wokół /), gdzie i to liczby całkowite
dodatnie. Jeśli odpowiedź jest liczbą całkowitą, to oczywiście .
Przykład
Dla danych wejściowych:
1
28
fb1da30d1b7230
poprawną odpowiedzią jest:
282/5
Przykład odpowiada rysunkowi, a ciąg bitów wygląda następująco:
1111 1011 0001 1101 1010 0011 0000 1101 0001 1011 0111 0010 0011 0000
Autor zadania: Szymon Acedański.