Overview

This is a problem where we determine the result of a game in which Takahashi and Aoki distribute gems flowing from a conveyor belt.

Analysis

In this problem, Takahashi keeps taking new gems as long as the total value of gems he has taken so far remains at most \(K\). Once it would exceed \(K\), he stops taking gems, and all subsequent gems go to Aoki.

The key observation is that “whether Takahashi takes a gem or not” is determined sequentially, and it depends on the simple condition of whether the total value exceeds \(K\) or not.

Due to this greedy behavior, the simulation can be completed in a single loop. That is, for each gem, we simply determine in order “whether Takahashi takes it or Aoki takes it,” so no complex processing such as sorting or recursion is needed.

A straightforward approach is unlikely to cause misunderstanding, but if one were to try something like “testing all possibilities,” it would not finish in time (TLE) since \(N\) can be up to \(2 \times 10^5\). However, since the greedy approach determines the optimal action in this problem, a simple simulation is sufficient.

Algorithm

1. Read the number of gems \(N\), the upper limit \(K\), and the value of each gem \(A_i\) from the input.
2. Initialize Takahashi’s total takahashi_sum and Aoki’s total aoki_sum (both to 0).
3. For each gem \(A_i\), do the following:
   • If takahashi_sum + A_i <= K, Takahashi takes that gem (add to takahashi_sum).
   • Otherwise, Aoki takes that gem (add to aoki_sum).
4. Finally, compare both totals and determine which is larger, or if it’s a tie, and output the result.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding input)

Implementation Notes

• Using map(int, input().split()) when reading input is efficient.

• The conditional branching only needs to check “Can Takahashi take this gem?”, so it can be handled with a single if statement.

• Don’t forget to check for equality in the final comparison (to handle the tie case).

  Source Code

N, K = map(int, input().split())
A = list(map(int, input().split()))

takahashi_sum = 0
aoki_sum = 0

for a in A:
    if takahashi_sum + a <= K:
        takahashi_sum += a
    else:
        aoki_sum += a

if takahashi_sum > aoki_sum:
    print("Takahashi")
elif aoki_sum > takahashi_sum:
    print("Aoki")
else:
    print("Draw")

This editorial was generated by qwen3-coder-480b.