시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
20 초 (추가 시간 없음) | 1024 MB | 22 | 21 | 13 | 100.000% |
Przypomnijmy jak wygląda drzewo binarne. Węzły tego drzewa będziemy numerowali kolejnymi liczbami naturalnymi od 1, idąc kolejnymi poziomami od góry do dołu poczynając od korzenia (wierzchołka na samej górze), a na każdym poziomie od lewej do prawej:
Drzewo binarne narysowane do węzła nr 18. Zwróć uwagę, że drzewo ma więcej niż 18 węzłów.
W tym zadaniu będziemy rozpatrywali najkrótsze ścieżki pomiędzy dwoma węzłami. Przykładowo, najkrótsza ścieżka między węzłami numer 8 oraz 5 ma trzy krawędzie i przebiega przez węzły 4 oraz 2.
Napisz program, który wczyta zapytania dotyczące ścieżek pomiędzy dwoma węzłami drzewa, dla każdego z nich wyznaczy długość najkrótszej ścieżki między tymi węzłami i wypisze wyniki na standardowe wyjście.
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q (1 ≤ Q ≤ 100 000), określająca liczbę zapytań. W kolejnych Q wierszach znajdują się zapytania, po jednym w wierszu. Opis każdego zapytania składa się z dwóch liczb naturalnych Ai oraz Bi (1 ≤ Ai, Bi ≤ 1018), oddzielonych pojedynczym odstępem i określających numery węzłów, dla których należy wyznaczyć ścieżkę.
Twój program powinien wypisać na wyjście Q wierszy. W i-tym z nich powinna się znaleźć liczba całkowita – liczba krawędzi, które należy pokonać, aby przedostać się w drzewie z węzła o numerze Ai do węzła Bi.
3 8 5 6 7 4 1
3 2 2
1 1 1000
9
4 10 20 20 10 10 1 1 10
1 1 3 3
1 1000000000 5000000000
61