QOJ.ac

QOJ

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

#6110. リスのゲーム

Statistics

Twinkle と Nova は国立公園を散歩しています。公園には $1, \dots, M$ の位置に $M$ 個の石が左から右へ並んでいます。また、$N$ 匹のリスが $x_1, \dots, x_N$ の位置にある石の上に、左から右へ並んでいます。リスはそれぞれ異なる石の上にいて、全員左を向いています。

Twinkle は Nova に次のようなゲームを提案しました。Twinkle と Nova は交互に手番を行います。各手番で、プレイヤーはリスが乗っていない石のいずれか 1 つにどんぐりを置かなければなりません。また、そのどんぐりの右側に少なくとも 1 匹のリスがいなければなりません。

どんぐりを置いた後、そのどんぐりの右側にいるリスのうち、最も左側にいる $K$ 匹が同時にどんぐりに向かって走り出します(どんぐりの右側にいるリスが $K$ 匹未満の場合は、そのすべてのリスが走り出します)。すべてのリスは同じ速さで走ります。いずれかのリスがどんぐりに到達した時点で、すべてのリスは直ちに停止します。どんぐりに到達したリスは、そのどんぐりを頬袋に入れ、石からどんぐりを取り除きます。

どんぐりを置くことができる有効な石が存在しない場合、その手番のプレイヤーは直ちに敗北します。Twinkle が先攻です。Twinkle と Nova が両者とも最適に行動した場合、どちらが勝つか判定してください。

ゲームの例 (M=7, N=3, K=2)

入力

入力は以下の形式で与えられます。

$M$ $N$ $K$ $x_1$ $x_2$ $\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.