DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

I Want to Play Jenga

Back to problem

Editorial

Number the five blocks in each layer as 1,2,3,4,51,2,3,4,51,2,3,4,5 from one end to the other. Block 333 is the center block.

The key is to pair blocks and answer every move by removing its paired block. From the center-of-mass condition in the statement, one can verify that in each of the paired configurations described below, whenever the opponent makes a move that does not collapse the tower, removing the paired block also does not collapse the tower. After the response, the projected center of mass above every layer boundary remains inside the convex hull of the remaining support region.

Suppose that HHH is odd. The topmost layer cannot be used, so an even number of layers are available for removals. Pair them from the bottom as (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).

If Shirogane removes block jjj from one layer of a pair, Shinomiya removes block jjj from the other layer of the same pair. By the stability observation above, this response is always possible. Every move is matched by another move, so Shirogane is the first player who has no safe move left. Thus Shinomiya wins when HHH is odd.

Now suppose that HHH is even. Shirogane first removes the center block, block 333, from layer H−1H-1H−1. The center of this block lies on the central vertical axis of the tower, so this removal does not shift the center of mass to either side and does not collapse the tower.

After that, pair layers 111 through H−2H-2H−2 as (1,2),(3,4),…,(H−3,H−2)(1,2),(3,4),\ldots,(H-3,H-2)(1,2),(3,4),…, and pair blocks with the same number across the two layers. Inside layer , pair block with block , and block with block . Whenever Shinomiya removes a block, Shirogane removes its paired block. Again, the stability condition guarantees that the response is safe. Except for Shirogane's first move, all moves are paired, so Shinomiya is the first player who has no safe move left.

Therefore the winner depends only on the parity of HHH.

  • If HHH is odd, print Shinomiya.
  • If HHH is even, print Shirogane.

Each test case is processed in O(1)O(1)O(1) time and O(1)O(1)O(1) extra space.

Solution written by GPT5.6

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