QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

#6110. 다람쥐 게임

Statistics

Twinkle과 Nova가 국립공원을 산책하고 있다. 공원에는 왼쪽부터 오른쪽으로 $1, \dots, M$의 위치에 $M$개의 돌이 놓여 있다. 또한 $x_1, \dots, x_N$ 위치의 돌 위에 $N$마리의 다람쥐가 있으며, 이들은 모두 왼쪽을 바라보고 있다. 각 다람쥐는 서로 다른 돌 위에 있다.

Twinkle은 Nova에게 다음과 같은 게임을 제안했다. Twinkle과 Nova는 번갈아 가며 차례를 갖는다. 자신의 차례가 되면, 플레이어는 다람쥐가 없는 돌 중 하나에 도토리를 놓아야 한다. 또한, 도토리의 오른쪽에는 반드시 하나 이상의 다람쥐가 있어야 한다.

도토리를 놓은 후, 도토리 오른쪽에 있는 다람쥐 중 가장 왼쪽에 있는 $K$마리의 다람쥐가 동시에 도토리를 향해 달리기 시작한다. (도토리 오른쪽에 다람쥐가 $K$마리보다 적다면, 모든 다람쥐가 달리기 시작한다.) 모든 다람쥐는 같은 속도로 달린다. 다람쥐 중 하나라도 도토리에 도달하면, 모든 다람쥐는 즉시 멈춘다. 도토리에 도달한 다람쥐는 도토리를 볼 주머니에 넣으며, 결과적으로 도토리는 돌에서 제거된다.

도토리를 놓을 수 있는 유효한 돌이 없으면, 현재 차례인 플레이어가 즉시 패배한다. Twinkle이 먼저 시작한다. Twinkle과 Nova가 모두 최적으로 플레이할 때 누가 이길지 결정하라.

예제 게임 (M=7, N=3, K=2)

입력

첫 번째 줄에는 세 개의 정수 $M, N, K$가 공백으로 구분되어 주어진다. 두 번째 줄에는 $N$개의 정수 $x_1, \dots, x_N$이 공백으로 구분되어 주어진다.

  • $1 \le N \le M \le 100\,000$
  • $1 \le K \le 10$
  • $1 \le x_1 < \dots < x_N \le M$

출력

Twinkle이 이기면 Twinkle을 출력하고, 그렇지 않으면 Nova를 출력한다.

예제

입력 1

7 3 2
1 4 7

출력 1

Nova

입력 2

7 3 1
1 4 7

출력 2

Twinkle

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#530Editorial Open集训队作业 解题报告 by 卢华睿Qingyu2026-01-02 21:49:02 Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.