DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

Yet Another Stone Game

返回题目

题解

후공이 이기는 상태를 패배 상태라고 하자. OOO를 홀수인 돌 더미의 개수, MMM을 모든 돌 더미 크기의 최솟값이라고 하자.

가능한 KKK는 N−2N-2N−2, N−1N-1N−1, NNN뿐이다. 단, N=3N=3N=3, K=1K=1K=1인 경우는 따로 처리한다.

K=1K=1K=1인 경우

한 번 행동할 때마다 전체 돌의 수가 정확히 111 감소한다. 따라서 게임의 전체 행동 횟수는 ∑Ai\sum A_i∑Ai​로 고정된다. 이 합이 짝수일 때만 패배 상태이다.

K=NK=NK=N인 경우

모든 돌 더미가 짝수인 상태가 정확히 패배 상태이다. 이 상태에서 한 번 행동하면 적어도 하나의 더미가 홀수가 된다. 반대로 홀수인 더미가 하나라도 있으면 홀수인 더미를 전부 골라 모든 더미를 짝수로 만들 수 있다.

K=N−1K=N-1K=N−1인 경우

모든 더미의 홀짝이 같은 상태가 정확히 패배 상태이다. 모든 더미가 짝수이거나 모든 더미가 홀수인 상태에서 111개 이상 N−1N-1N−1개 이하의 더미를 고르면 두 홀짝이 섞인다. 반대로 두 홀짝이 섞인 상태에서는 홀수인 더미를 전부 골라 모든 더미를 짝수로 만들 수 있다.

K=N−2K=N-2K=N−2인 경우

이 경우에는 N≥4N\geq4N≥4이다. 다음 두 종류가 정확히 패배 상태이다.

  • 모든 더미가 짝수이다.
  • 홀수인 더미가 N−1N-1N−1개이고, 유일한 짝수 더미의 크기가 전체의 최솟값이다.

첫 번째 상태에서 행동하면 홀수인 더미가 111개 이상 N−2N-2N−2개 이하가 되므로 두 패배 상태 중 어느 것도 될 수 없다.

두 번째 상태에서 모든 더미를 짝수로 만들려면 N−1N-1N−1개의 홀수 더미를 모두 골라야 하므로 불가능하다. 같은 종류의 상태로 이동하려면 유일한 짝수 더미와 홀수 더미 하나를 함께 골라야 한다. 그러면 기존의 최솟값이 111 감소하여 홀수가 되고, 새로 짝수가 된 더미보다 작아진다. 따라서 새 유일한 짝수 더미가 최솟값일 수 없다. 즉, 패배 상태에서 다른 패배 상태로 이동할 수 없다.

이제 위 두 종류가 아닌 상태에서 패배 상태로 이동할 수 있음을 보이자.

  • 홀수 더미가 111개 이상 N−2N-2N−2개 이하라면, 홀수 더미를 모두 골라 모든 더미를 짝수로 만든다.
  • 모든 더미가 홀수라면, 최솟값인 더미 하나를 골라 유일한 짝수이자 최솟값으로 만든다.
  • 홀수 더미가 N−1N-1N−1개이지만 유일한 짝수 더미가 최솟값이 아니라면, 그 짝수 더미와 최솟값인 홀수 더미를 고른다. 그러면 후자가 유일한 짝수이자 최솟값이 된다.

따라서 각 테스트 케이스에서 OOO, MMM, 돌의 합만 계산하면 된다. 시간 복잡도는 O(N)O(N)O(N)이고, 추가 공간 복잡도는 O(1)O(1)O(1)이다.

Solution written by GPT6