머핀 게임

Alf와 Beata는 아주, 아주 오래전, 오후를 프로그래밍 대회로 보낼 수 없었던 시대에 살던 두 젊은이였다. 따라서 그들의 삶은 오늘날 젊은이들의 삶보다 훨씬 지루했다. 컴퓨터 없이 어떻게 살아남을 수 있느냐고 생각할지도 모른다. 답은 간단하다. 베이킹을 하는 것이다!

두 젊은이는 머핀 굽기를 좋아했고, 다 굽고 나면 머핀이 흔히 큰 더미로 쌓였다. 부엌을 머핀으로 가득 채우지 않기 위해 Beata는 매일 저녁 친구에게 머핀 게임으로 승부를 걸었다.

머핀 게임은 두 플레이어(여기서는 Alf와 Beata)와 $N$개의 머핀이 쌓인 큰 더미로 진행한다. 이제 플레이어들은 번갈아 가며 행동한다. 한 번의 행동에서 플레이어 $A$은 머핀 더미를 두 부분으로 나눈다(두 더미 중 하나는 비어 있을 수도 있다). 그러면 상대 플레이어가 두 더미 중 하나를 선택하고, 그 더미의 머핀을 모두 먹는다. 다음 행동에서는 플레이어들의 역할이 바뀌어, 플레이어 $B$이 머핀 더미를 나누고 플레이어 $A$이 두 더미 중 하나를 먹는다. 모든 머핀이 없어질 때까지 이와 같이 번갈아 진행한다.

Alf가 먼저 행동한다(즉, 큰 더미를 나눈다). Beata는 두 더미 중 하나를 먼저 먹는다. 두 사람 모두 가능한 한 잘 플레이한다면(즉, 각자 가능한 한 많은 머핀을 먹으려 한다면), 게임이 진행되는 동안 Alf와 Beata가 각각 몇 개의 머핀을 먹게 되는지 계산할 수 있는가?

힌트: 머핀 더미를 나눌 때는 항상 두 더미의 크기가 가능한 한 같아지도록 나누는 것이 좋다(예제 설명을 참고한다).

채점

• 절반의 점수를 받으려면 $N \le 20$인 테스트 케이스를 해결해야 한다.

• 만점을 받으려면 $N \le 10\,000$인 테스트 케이스를 해결해야 한다.

입력의 첫 번째이자 유일한 줄에 처음 더미에 들어 있는 머핀의 수를 나타내는 정수 $N$이 주어진다.

두 사람이 모두 가능한 한 잘 플레이할 때 Alf가 먹게 되는 머핀의 수와 Beata가 먹게 되는 머핀의 수, 두 정수를 출력한다.

머핀이 하나뿐이므로 Alf가 할 수 있는 유일한 분할은 빈 더미 하나와 머핀 하나가 들어 있는 더미 하나로 나누는 것이다. 그러면 Beata가 머핀 하나가 들어 있는 더미를 먹는다.

여기서 Alf는 머핀을 하나만 얻을 수 있다. 첫 번째 라운드에서 그는 머핀 더미를 각각 2개의 머핀이 든 두 더미로 나눈다. Beata는 2개의 머핀을 먹고, 남은 더미를 각각 1개의 머핀이 든 2개의 더미로 나눈다. Alf는 머핀 하나를 먹은 뒤 마지막 머핀을 Beata에게 줄 수밖에 없다.