← 返回题目列表

AtCoder · kupc2018_j

J. 尼姆?

中文机器翻译题面 查看原题

配点 : 400 点

問題文

一堆硬币 有 N 件。

在山里 它们的编号最大为 1 到 N ,i 第一座山是 由 a_i 硬币组成。

使用这些硬币堆来创建以下内容 2 考虑一下人类游戏。

  • 玩家分为先玩者和后玩者。
  • 从第一个玩家开始,每个玩家轮流进行。轮到你时,执行以下操作 2 按顺序执行两个操作。 小于或等于
    1. K 的正整数 声明 x 。
      然而,彼此 2 在随后的回合中,该数字小于上一回合中声明的整数。 请勿声明 x 。 一堆至少包含
    2. x 枚硬币 1 选择一个并从硬币堆中取出一枚硬币。 x 删除。
      如果不存在这样的山,游戏就在那里结束,另一位玩家赢得游戏。

Chinatsu-san 和 Akari-san 玩这个游戏,Chinatsu-san 玩第一,Akari-san 玩第二。 我决定重复 M 次。

但是 1 每局游戏结束后,该局游戏中取出的金币应放回原堆。

顺便说一句,由于千夏小姐和明里小姐都以最佳方式获胜,所以如果游戏开始时每堆金币的数量没有变化,那么游戏的结果不会改变,也不会有趣。

有 2 人们是i (1 \leq i \leq M - 1) 第一局游戏结束后,取出的硬币返回到原来的一堆,b_i 第堆硬币 c_i 我决定增加数量。

M 每场比赛,决定千夏和明里谁获胜。

制約

  • 所有输入均为整数
  • 1 \leq N \leq 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq M \leq 10^5
  • 1 \leq a_i \leq 10^9
  • 1 \leq b_i \leq N
  • 1 \leq c_i \leq 10^9

部分点

如果您对满足以下所有附加约束的数据集回答正确,30 点。

  • N = 1
  • M = 1

如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 370 点。


入力

输入将以以下形式从标准输入给出。

N K M
a_1 a_2 ... a_N
b_1 c_1
:
b_{M - 1} c_{M - 1}

出力

i 行中,i 如果第二局千夏(先手)获胜 Chinatsu ,如果 Akari(第二位玩家)获胜 输出 Akari 。


入力例 1

1 8 1
7

出力例 1

Chinatsu

先走的千夏可以在第一回合从唯一的一堆硬币中取出所有硬币。
此时,在 Akari 的下一个回合中,无论她声明什么正整数,她都无法选择包含更多硬币的一堆。
因此,千夏赢得了比赛。
该输入示例满足部分点相加约束。


入力例 2

1 1 1
2

出力例 2

Akari

彼此 只能声明 1 。
这时,在千夏第一个转弯时,千夏从山上移动了。 取出 1 硬币。
然后,在明里的下一个回合,明里 1 硬币。
2 轮到千夏了,千夏 您无法选择包含超过 1 枚硬币的一堆。
因此,Akari 赢得了比赛。
该输入示例满足部分点相加约束。


入力例 3

5 7 3
83795 19140 82706 34385 26675
2 74621
3 60951

出力例 3

Chinatsu
Akari
Chinatsu