원숭이 안 떨어뜨리기

원숭이 수의 합을 $S$라 하자. 각 턴에 층 하나를 제거하므로 총 $H$턴이다. 마지막 턴을 맡지 않는 사람을 $P$라 하자.

$P$의 턴에는 남은 층이 항상 짝수 개이므로 적어도 $2$개이다. 따라서 $P$는 매번 현재 맨 아래층이 아닌 층을 제거할 수 있다. 이때 원숭이는 다른 층으로 이동하므로 $P$는 원숭이를 가져가지 않는다. 이 전략으로 $P$는 상대의 행동과 무관하게 $0$마리를 보장하며, 이보다 적게 가져갈 수는 없으므로 최적이다.

게임이 끝나면 모든 원숭이는 두 사람 중 한 명에게 있으므로, 마지막 턴을 맡는 사람은 $S$마리를 가져가게 된다. $H$가 홀수이면 Ishigami가 마지막 턴을 맡아 결과는 $(S,0)$이고, 짝수이면 결과는 $(0,S)$이다. $S=0$이어도 같은 식이 성립한다.

입력을 읽으며 합을 구하면 시간복잡도는 $O(H)$, 추가 공간복잡도는 $O(1)$이다. $S \le 10^{15}$이므로 합과 출력은 부호 있는 $64$비트 정수로 계산한다.

Solution written by GPT