← 返回题目列表

AtCoder · arc174_f

F. 最后阶段

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

积分: 900 点

问题陈述

玩家 Alice 和 Bob 使用序列玩游戏 L 和 R 长度 N,如下。

  • 游戏包括 N 转。
  • If i 为奇数,转 i 由Alice扮演;如果 i 为偶数,转 i 由鲍勃扮演。
  • 最初,有一堆装有一定数量的石头。
  • 对于 i=1,2,\dots,N 按照此顺序,它们执行以下操作(称为转 i):
    • 进行回合的玩家 i 之间取整数个石子 L_i 和 R_i,包含在内,来自堆。
    • 如果玩家不能拿走满足上述条件的棋子,他们就输了,另一位玩家获胜。
  • 如果回合结束时双方都没有输 N,比赛以平局结束。

游戏开始前,双方玩家都会被告知顺序 L 和 R 以及游戏开始时堆中石子的数量。

可以证明该游戏恰好具有以下三种之一 后果:

  • Alice ...爱丽丝有一个获胜策略。
  • Bob ...鲍勃有一个制胜策略。
  • Draw ...两位玩家都没有获胜策略。

答案 Q 有关此游戏的查询。的 i第查询如下:

  • 假设该堆包含 C_i 游戏开始时的棋子。汇报比赛结果: Alice, Bob,或 Draw.

约束

  • N, L_i, R_i, Q,和 C_i 是整数。
  • 1 \le N \le 3 \times 10^5
  • 1 \le L_i \le R_i \le 10^9
  • 1 \le Q \le 3 \times 10^5
  • 1 \le C_i \le \sum_{i=1}^{N} R_i

输入

输入由标准输入按以下格式给出:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N
Q
C_1
C_2
\vdots
C_Q

输出

打印 Q 行。 的 i- 第行应包含以下问题的答案 i第一个查询。


示例输入 1

4
1 3
1 2
3 4
1 2
11
1
2
3
4
5
6
7
8
9
10
11

示例输出 1

Alice
Alice
Alice
Bob
Bob
Alice
Alice
Alice
Draw
Draw
Draw

该输入包含 11 查询。

  • 当 C_i \le 3, Alice 可以拿走所有 C_i 转牌石子 1,堆里没有留下任何石头,所以爱丽丝有一个获胜的策略。
  • 当 4 \le C_i \le 5,鲍勃有一个制胜策略。
  • 当 6 \le C_i \le 8,爱丽丝有一个获胜的策略。
  • 当 C_i \ge 9,两位玩家都没有获胜策略。
    • 例如,如果 牌匾上写着 C_i=9,游戏可以按如下方式进行:
      • 开启 1,爱丽丝采取 3 石头。 6 石头依然存在。
      • 开启 2,鲍勃采取 1 石头。 5 石头依然存在。
      • 开启 3,爱丽丝采取 4 石头。 1 石头遗迹。
      • 开启 4,鲍勃采取 1 石头。没有留下任何石头。
      • 由于到回合结束时双方都没有输 4,比赛以平局结束。
    • 各种其他进展都是可能的,但可以证明,当 C_i=9,双方都没有获胜策略(如果双方都发挥最佳,则游戏将以平局结束)。