Overview

Calculate the total score \(t\) that Takahashi obtains by following the rules, and the remaining total score \(a\) (for Aoki), then compare \(t\) and \(a\) to determine the winner.

Analysis

The key point of this problem is that Takahashi’s actions are completely fixed, even though it is described as a “game.”
At the moment each gem \(A_i\) arrives:

• If the current total is \(t\) and \(t + A_i \le K\), he must take it
• Otherwise, he does not take it

Since this is fully determined, there are no branches or strategies. In other words, all we need is a single simulation processing from left to right.

Additionally, since Aoki “receives all the gems that Takahashi did not take,” Aoki’s total can be computed in one step using: - The overall sum \(S = \sum A_i\) - Takahashi’s total \(t\)

as \(a = S - t\).

Naively exploring all “take/don’t take” combinations or thinking of it as a knapsack DP would never be fast enough for \(N \le 2\times 10^5\) (and it’s unnecessary since there is no freedom of choice in the first place).

Example: - \(K=10,\ A=[6,5,4]\) - 6: \(0+6\le 10\), so take it → \(t=6\) - 5: \(6+5>10\), so don’t take it → \(t=6\) - 4: \(6+4\le 10\), so take it → \(t=10\) - Sum \(S=15\), so Aoki gets \(a=15-10=5\), Takahashi wins

Algorithm

1. Initialize \(t=0\) (Takahashi’s total) and \(S=0\) (overall sum).
2. Iterate through the array from the beginning. For each \(x=A_i\):
   • \(S \leftarrow S + x\)
   • If \(t + x \le K\), then \(t \leftarrow t + x\) (Takahashi takes it)
3. Aoki’s total is \(a = S - t\).
4. Compare \(t\) and \(a\):
   • If \(t>a\), output Takahashi
   • If \(t<a\), output Aoki
   • If equal, output Draw

Complexity

• Time complexity: \(O(N)\) (a single pass only)
• Space complexity: \(O(1)\) (constant excluding the input array; \(O(N)\) if the array is stored in the implementation)

Implementation Notes

• Since \(K \le 10^{15}\) and the total sum can also be large, 64-bit integers are required (Python’s int handles this safely).

• With input size up to \(2\times 10^5\), using sys.stdin.readline in Python ensures stable performance.

• Computing Aoki’s score as “total sum minus Takahashi’s score” is simpler and less error-prone than “summing up the gems not taken.”

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    t = 0
    total = 0
    for x in A:
        total += x
        if t + x <= K:
            t += x
    a = total - t
    if t > a:
        print("Takahashi")
    elif t < a:
        print("Aoki")
    else:
        print("Draw")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.