젠가가 하고 싶어

각 층의 블록을 한쪽 끝에서부터 $1,2,3,4,5$번 블록이라 하자. 가운데 블록은 $3$번이다.

핵심은 서로 대응되는 두 블록을 정해 두고 상대가 한쪽을 제거하면 다른 한쪽을 제거하는 것이다. 문제에서 정의한 무게중심 조건에 따라 계산하면, 아래에서 설명하는 대응 관계가 유지된 상태에서는 상대가 탑을 무너뜨리지 않는 수를 두었을 때 대응되는 블록을 제거하는 수 역시 탑을 무너뜨리지 않는다. 대응 수를 둔 뒤에는 각 층 경계에서 위쪽 블록들의 무게중심 투영점이 남은 블록들의 지지 영역의 볼록껍질 안에 유지된다.

$H$가 홀수라고 하자. 가장 위층은 제거할 수 없으므로 블록을 제거할 수 있는 층은 짝수 개이다. 아래에서부터 $(1,2),(3,4),\ldots,(H-2,H-1)$처럼 두 층씩 짝짓는다.

Shirogane가 한 쌍의 한 층에서 $j$번 블록을 제거하면 Shinomiya는 같은 쌍의 다른 층에서 $j$번 블록을 제거한다. 위의 안정성 관찰에 의해 이 대응 수는 항상 가능하다. 모든 수가 둘씩 대응되므로 Shirogane가 먼저 더 이상 안전한 수를 둘 수 없게 된다. 따라서 $H$가 홀수이면 Shinomiya가 이긴다.

$H$가 짝수라고 하자. Shirogane는 먼저 $H-1$층의 가운데인 $3$번 블록을 제거한다. 이 블록의 중심은 탑의 중심축 위에 있으므로 이 수로 무게중심이 한쪽으로 치우치지 않으며 탑은 쓰러지지 않는다.

그 뒤 $1$층부터 $H-2$층까지는 $(1,2),(3,4),\ldots,(H-3,H-2)$처럼 두 층씩 짝짓고 같은 번호의 블록끼리 대응시킨다. 층에서는 번과 번, 번과 번을 각각 대응시킨다. Shinomiya가 어느 블록을 제거하더라도 Shirogane는 그 대응 블록을 제거한다. 역시 안정성 조건에 의해 대응 수는 항상 가능하다. 첫 수를 제외한 모든 수가 둘씩 대응되므로 이번에는 Shinomiya가 먼저 더 이상 안전한 수를 둘 수 없게 된다.

따라서 정답은 $H$의 홀짝만으로 결정된다.

• $H$가 홀수이면 Shinomiya.
• $H$가 짝수이면 Shirogane.

각 테스트 케이스를 $O(1)$ 시간과 $O(1)$ 추가 공간에 처리할 수 있다.

Solution written by GPT5.6