Displacing Particles

시간 제한1초메모리 제한1024 MB

요약

한 변의 길이가 2^N인 정사각형의 중심에서 시작해 네 꼭짓점 중 하나로 거리를 절반씩 줄여 나갈 때, 점 (x, y)에 도달하는 최소 횟수를 구한다.

난이도: 보통10점 중 6점
유형: 수학, 분할 정복, 비트 연산, 기하
정답자: 아직 제출이 없습니다

문제

A square has its vertices at the coordinates $(0, 0)$ , $(0, 2^N)$ , $(2^N , 2^N )$ , $(2^N , 0)$ . Each vertex has an attractor. A particle is placed initially at position $(2^{N-1} , 2^{N-1})$ . Each attractor can be activated individually, any number of times. When an attractor at position $(i, j)$ is activated, if a particle is at position $(p, q)$ , it will be moved to the midpoint between $(i, j)$ and $(p, q)$ .

Given $N$ and a point $(x, y)$ , calculate the least number of times you have to activate the attractors so that the particle ends up at position $(x, y)$ .

입력

The input consists of a single line containing three integers $N$ , $x$ and $y$ , such that $1 ≤ N ≤ 20$ and $0 < x, y < 2^N$ .

출력

Print a single line, containing the least number of times you have to active the attractors.

예제3

예제 1
입력
```
1 1 1
```
예상 출력
```
0
```
예제 2
입력
```
4 12 4
```
예상 출력
```
1
```
예제 3
입력
```
4 3 1
```
예상 출력
```
3
```