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

Yet Another Stone Game

Back to problem

Editorial

Call a position losing if the second player wins from it. Let OOO be the number of piles with an odd size, and let MMM be the minimum pile size.

The only possible values of KKK are N−2N-2N−2, N−1N-1N−1, and NNN. We handle the special case N=3N=3N=3, K=1K=1K=1 separately.

Case K=1K=1K=1

Every move decreases the total number of stones by exactly one, so the game always lasts ∑Ai\sum A_i∑Ai​ moves. The position is losing exactly when this sum is even.

Case K=NK=NK=N

A position is losing exactly when all piles are even. Any move from such a position creates at least one odd pile. Conversely, if an odd pile exists, choose all odd piles to make every pile even.

Case K=N−1K=N-1K=N−1

A position is losing exactly when all pile sizes have the same parity. From an all-even or all-odd position, choosing between one and N−1N-1N−1 piles makes the parities mixed. Conversely, from a mixed position, choose every odd pile to make all piles even.

Case K=N−2K=N-2K=N−2

Here N≥4N\geq4N≥4. Exactly the following positions are losing.

  • Every pile is even.
  • Exactly N−1N-1N−1 piles are odd, and the unique even pile has the minimum size.

From the first type, a move creates between one and N−2N-2N−2 odd piles, so neither losing type can be reached.

From the second type, making every pile even would require choosing all N−1N-1N−1 odd piles, which is impossible. To reach another position of the second type, the unique even pile and exactly one odd pile would have to be chosen. The old minimum then decreases by one and becomes odd, making it smaller than the new unique even pile. Thus, the new even pile is not a minimum. No move goes from a losing position to another losing position.

It remains to show that every other position can reach a losing position.

  • If there are between one and N−2N-2N−2 odd piles, choose all odd piles to make every pile even.
  • If all piles are odd, choose one minimum pile. It becomes the unique even pile and remains a minimum.
  • If exactly N−1N-1N−1 piles are odd but the unique even pile is not a minimum, choose that even pile and a minimum odd pile. The latter becomes the unique even pile and the minimum.

Therefore, it is enough to compute OOO, MMM, and the total number of stones for each test case. The time complexity is O(N)O(N)O(N), and the additional space complexity is O(1)O(1)O(1).

Solution written by GPT6