Drzewko (이진 트리)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	1004	833	483	48.529%

문제

Mamy dane drzewko binarne o wysokości h (jak na rysunku):

높이가 h인 이진 트리가 주어집니다 (그림과 같이):

Każda krawędź może być zamknięta bądź otwarta. Początkowo otwarte są wszystkie lewe krawędzie (zaznaczone linią przerywaną). Adrianek zrzuca po kolei n piłeczek, poczynając od wierzchołka startowego, który jest korzeniem drzewa. Każda piłeczka zawsze leci przez otwartą krawędź, a następnie zmienia ją na zamkniętą oraz otwiera sąsiednią krawędź (gdy otwarta jest lewa krawędź, to zamykamy lewą i otwieramy prawą, a gdy otwarta jest prawa, to zamykamy prawą i otwieramy lewą).

각 간선은 닫혀 있거나 열려 있을 수 있습니다. 처음에는 모든 왼쪽 간선이 열려 있습니다 (점선으로 표시됨). Adrianek은 트리의 루트인 시작 정점에서부터 연속해서 n개의 공을 떨어뜨립니다. 각 공은 항상 열린 간선을 통해 떨어지며, 그 후 해당 간선을 닫고 인접한 간선을 엽니다 (왼쪽 간선이 열려 있을 때는 왼쪽을 닫고 오른쪽을 열며, 오른쪽 간선이 열려 있을 때는 오른쪽을 닫고 왼쪽을 엽니다).

Adrianek zastanawia się, do którego wierzchołka (ponumerowanego od 0 do 2h - 1) spadnie n-ta piłeczka.

Adrianek은 n번째 공이 어느 정점 (0부터 2h - 1까지 번호가 매겨진)으로 떨어질지 궁금해합니다.

입력

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite n, h (1 ≤ n ≤ 10^8, 0 ≤ h ≤ 30), oznaczające odpowiednio liczbę piłeczek zrzucanych przez Adrianka oraz wysokość drzewka binarnego.

표준 입력의 첫 번째 줄에는 두 개의 정수 n, h (1 ≤ n ≤ 10^8, 0 ≤ h ≤ 30)가 주어집니다. 이는 각각 Adrianek이 떨어뜨리는 공의 개수와 이진 트리의 높이를 나타냅니다.

출력

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą numerze wierzchołka, do którego spadnie n-ta piłeczka.

표준 출력의 첫 번째이자 유일한 줄에는 n번째 공이 떨어질 정점의 번호와 같은 하나의 정수를 출력해야 합니다.

예제 입력 1

4 2

예제 출력 1

힌트

Piłeczki będą spadały kolejno do wierzchołków o numerach: 0, 2, 1, 3.

공들은 차례대로 다음 번호의 정점으로 떨어질 것입니다: 0, 2, 1, 3.

출처

Camp > ILOCAMP Science Camps > ILOCAMP 2011 (Intermediate Group) 1-1번

알고리즘 분류

수학
트리
비트마스킹

저작자표시 비영리 변경금지