← 返回题目列表

AtCoder · agc064_c

C. 擦除和分割游戏

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

分数: 900 点

问题陈述

高桥和青木将进行以下游戏。

  1. 对于每个 i=1,2,\ldots,N 按照此顺序,执行以下操作。
    • 写入每个整数 l_i 通过 r_i 一次在黑板上。 (这里, l_i 和 r_i 是输入中的非负整数。)
  2. 当一个或多个整数写在黑板上时,玩家轮流执行以下操作,高桥先行。
    • 选择并执行以下两个操作之一。
      • 删除黑板上写的所有偶数,并将剩余的每个整数替换为向下舍入为整数的一半。
      • 删除黑板上写的所有奇数,并将剩余的每个整数替换为其值的一半。
  3. 当黑板上没有写出整数时,游戏结束,最后执行操作的玩家获胜。

可以证明,如果高桥和青木表现最佳,则游戏会在有限次数的操作中结束。找出本例中的获胜者。

解决上述问题 T 案例。

约束

  • 1 \leq T \leq 10^4
  • 1 \leq N \leq 10^4
  • 0 \leq l_i \leq r_i \leq 10^{18}
  • r_i \lt l_{i+1}
  • 总和 N 单个输入中的测试用例最多 10^4.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出,其中 \mathrm{test}_i 代表 i-第一个测试用例:

T
\mathrm{test}_1
\vdots
\mathrm{test}_T

每个测试用例均按以下格式给出:

N
l_1 r_1
\vdots
l_N r_N

输出

打印 T 行。的 i- 第行应包含 Takahashi 如果高桥在比赛中获胜 i第一个测试用例,以及 Aoki 如果青木获胜。


示例输入 1

3
2
1 2
5 7
1
0 100
10
1312150450968413 28316250877914571
74859962623690078 84324828731963974
148049062628894320 252509054433933439
269587449430302150 335408917861648766
349993004923078531 354979173822804781
522842184971407769 578223540024979436
585335723211047194 615812229161735895
645762258982631926 760713016476190622
779547116602436424 819875141880895723
822981260158260519 919845426262703496

示例输出 1

Aoki
Aoki
Takahashi

以下是第一个测试用例的游戏情况示例。 黑板上写了一次

  • 每个 1,2,5,6,7 。
  • 高桥选择删除奇数。 1,5,7 从黑板上删除,剩下的整数 2,6 被替换为其值的一半,即 1,3。
  • 青木选择删除奇数。 1,3 从黑板上被删除,并且黑板上不再写任何整数,因此游戏结束,执行最后一个操作的青木获胜。