分数: 266 分
问题陈述
高桥和青木正在玩一个游戏,他们分发在传送带上流动的宝石。
游戏开始时,一个正整数 K 被确定。这是高桥能拿走的宝石总价值的上限。
N 宝石按顺序在传送带上流动,从 1-st 到 N-th。的价值 i-th 宝石是 A_i (正整数)。
每次有宝石流过时,高桥是否拿走它是根据以下规则决定的:
- 如果拿走宝石的话最多保留他目前为止拿走的宝石总价值(包括这颗宝石) K,他拿走了宝石。
- 否则(如果拿走宝石会导致总数超过 K),他没有拿走宝石。
也就是说,高桥贪婪地从第一个开始按顺序拿宝石,只要总数不超过 K.
青木收到了高桥没有拿走的所有宝石。青木在这件事上别无选择。
毕竟 N 宝石流过,高桥拿走的宝石总价值和青木收到的宝石总价值进行比较。总分多者获胜,总分相等则平局。
给定宝石数量 N,上限 K,以及值的序列 N 宝石 A_1, A_2, \ldots, A_N,判定比赛结果。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{15}
- 1 \leq A_i \leq 10^9
- 所有输入均为整数
输入
N K A_1 A_2 \ldots A_N
- 第一行包含整数 N 代表宝石数量和整数 K 代表高桥能拿走的宝石总价值上限,中间用空格隔开。
- 第二行包含的值 N 宝石 A_1, A_2, \ldots, A_N 按照它们流动的顺序,用空格分隔。
输出
如果高桥获胜,则打印 Takahashi;如果 Aoki 获胜,则打印 Aoki;如果是平局,则打印 Draw,在一行上。
示例输入 1
5 10 3 4 2 8 1
示例输出 1
Takahashi
示例输入 2
6 5 2 4 3 1 5 3
示例输出 2
Aoki
示例输入 3
8 15 5 3 4 6 2 7 1 2
示例输出 3
Draw