각 층의 블록을 한쪽 끝에서부터 번 블록이라 하자. 가운데 블록은 번이다.
핵심은 서로 대응되는 두 블록을 정해 두고 상대가 한쪽을 제거하면 다른 한쪽을 제거하는 것이다. 문제에서 정의한 무게중심 조건에 따라 계산하면, 아래에서 설명하는 대응 관계가 유지된 상태에서는 상대가 탑을 무너뜨리지 않는 수를 두었을 때 대응되는 블록을 제거하는 수 역시 탑을 무너뜨리지 않는다. 대응 수를 둔 뒤에는 각 층 경계에서 위쪽 블록들의 무게중심 투영점이 남은 블록들의 지지 영역의 볼록껍질 안에 유지된다.
가 홀수라고 하자. 가장 위층은 제거할 수 없으므로 블록을 제거할 수 있는 층은 짝수 개이다. 아래에서부터 처럼 두 층씩 짝짓는다.
Shirogane가 한 쌍의 한 층에서 번 블록을 제거하면 Shinomiya는 같은 쌍의 다른 층에서 번 블록을 제거한다. 위의 안정성 관찰에 의해 이 대응 수는 항상 가능하다. 모든 수가 둘씩 대응되므로 Shirogane가 먼저 더 이상 안전한 수를 둘 수 없게 된다. 따라서 가 홀수이면 Shinomiya가 이긴다.
가 짝수라고 하자. Shirogane는 먼저 층의 가운데인 번 블록을 제거한다. 이 블록의 중심은 탑의 중심축 위에 있으므로 이 수로 무게중심이 한쪽으로 치우치지 않으며 탑은 쓰러지지 않는다.
그 뒤 층부터 층까지는 처럼 두 층씩 짝짓고 같은 번호의 블록끼리 대응시킨다. 층에서는 번과 번, 번과 번을 각각 대응시킨다. Shinomiya가 어느 블록을 제거하더라도 Shirogane는 그 대응 블록을 제거한다. 역시 안정성 조건에 의해 대응 수는 항상 가능하다. 첫 수를 제외한 모든 수가 둘씩 대응되므로 이번에는 Shinomiya가 먼저 더 이상 안전한 수를 둘 수 없게 된다.
따라서 정답은 의 홀짝만으로 결정된다.
Shinomiya.Shirogane.각 테스트 케이스를 시간과 추가 공간에 처리할 수 있다.
Solution written by GPT5.6