토너먼트 (Baekjoon 1057)

문제 설명

토너먼트: 경기 때마다 패자를 제외시켜 최후에 남은 둘이서 우승을 결정하게 하는 시합
N명(N<=100,000)의 참가자는 1~N번까지 배정을 받는다. 그리고 난 후, 서로 인접한 번호끼리 스타를 한다.
만약 그 라운드의 참가자가 홀수라면, 마지막 번호를 가진 참가자는 자동으로 다음 라운드를 진출한다.
매 라운드마다 다시 번호를 배정받는다.(순서는 유지)
김지민, 임한수가 대회에 참가했다. 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정하고 몇 라운드에서 대결하는지 구해야 한다.

위 두가지 경우는 절대 대결할 수 없다. 인접한 번호가 아니기 때문이다.

그렇다면, 김지민의 번호와 임한수의 번호 차이가 1이 나면 무조건 대결하는가?
아니다! 1 2 3 4가 존재하는 경우, 1-2가 대결하고 3-4가 대결한다. 2와 3은 인접하지만 대결하지 않는다.
이를 생각해 짝수번호 = 홀수번호 + 1를 만족하는지 확인한다.

이를 만족한다면, 김지민과 임한수가 대결할 수 있는 조건이 된다.

이것을 보며 다음 라운드 번호를 가지는 규칙을 찾을 수 있었다.