← 返回题目列表

AtCoder · awc0026_b

B. 珠宝分布

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

分数: 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