저녁 메뉴 월드컵

문제

태우는 오늘도 저녁에 무엇을 먹을지 정하지 못해 고민하고 있다. 고민 끝에, 저녁 메뉴를 정하기 위해 N개의 후보 메뉴를 놓고 토너먼트를 진행하기로 했다. 토너먼트는 다음 규칙에 따라 메뉴가 1개 남을 때까지 반복하여 진행한다.

현재 M개의 메뉴가 남아있을 때, 남아있는 메뉴를 임의로 둘씩 짝지어 \left\lfloor \frac{M}{2} \right\rfloor개의 쌍을 만든다.
각 쌍에 대해 경기를 치른 뒤 승리하는 메뉴가 다음 라운드에 진출한다.
M이 홀수여서 짝을 짓지 못한 메뉴는 부전승으로 다음 라운드에 진출한다.

태우는 N개의 메뉴로 토너먼트를 진행할 때 부전승이 몇 번 발생하는지 궁금해졌다. 태우를 도와 부전승이 발생하는 횟수를 구하여라.

예제

3keyboard_return
13keyboard_return
17keyboard_return
8

2keyboard_return
4keyboard_return
0

첫 번째 테스트 케이스는 총 13개의 메뉴가 주어진다.

경기가 진행되는 경우의 수 중 하나의 시나리오는 다음과 같다.

다른 결과가 나왔더라도 부전승의 횟수는 언제나 2 번 일어난다.

두 번째 테스트 케이스는 총 17개의 메뉴가 주어진다.

경기가 진행되는 경우의 수 중 하나의 시나리오는 다음과 같다.

1 라운드: 1 vs 2, 3 vs 4, 5 vs 6, 7 vs 8, 9 vs 10, 11 vs 12, 13 vs 14, 15 vs 16, 17 부전승
2 라운드: 2 vs 3, 6 vs 8, 9 vs 12, 13 vs 15, 17 부전승
3 라운드: 2 vs 6, 12 vs 15, 17 부전승
4 라운드: 6 vs 15, 17 부전승
5 라운드: 15 vs 17

다른 결과가 나왔더라도 부전승의 횟수는 언제나 4 번 일어난다..

세 번째 테스트 케이스는 총 8개의 메뉴가 주어진다.

경기가 진행되는 경우의 수 중 하나의 시나리오는 다음과 같다.

다른 결과가 나왔더라도 부전승의 횟수는 언제나 0 번 일어난다.

태그

저녁 메뉴 월드컵 1s 1024MB