DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

I Want to Play Jenga

問題に戻る

解説

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

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

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

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

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

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

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

  • HHH가 홀수이면 Shinomiya.
  • HHH가 짝수이면 Shirogane.

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

Solution written by GPT5.6

(
H
−
3,H−
2)
H−1H-1H−1
111
555
222
444