Overview

This is a problem where gems flow on a conveyor belt, Takahashi picks them up following the rule “always take if the total stays at most \(K\),” and Aoki receives the remaining gems. We need to determine whose total is larger.

Analysis

First, let’s precisely understand Takahashi’s action rule.

• Gems flow one at a time in order.
• If “the sum of gems taken so far + the current gem’s value” is at most \(K\), Takahashi must take it.
• If it would exceed \(K\), he does not take it.
• Aoki receives all gems that Takahashi did not take.

In other words, Takahashi’s behavior is completely deterministic (no room for choice), so the answer can be found by simply simulating the process.

Concrete example: For \(N = 4\), \(K = 5\), \(A = [3, 4, 2, 1]\)

Final result: Takahashi \(5\), Aoki \(5\) → Draw

This problem does not require any special algorithms or data structures and can be solved with a simple simulation that examines gems from the beginning in order. Since \(N\) is at most \(2 \times 10^5\), a single \(O(N)\) loop is more than sufficient.

Algorithm

1. Initialize Takahashi’s total takahashi and Aoki’s total aoki to \(0\).
2. Examine gems in the order they flow (\(A_1, A_2, \ldots, A_N\)).
   • If takahashi + a <= K, Takahashi takes it → takahashi += a
   • Otherwise, Aoki receives it → aoki += a
3. Finally, compare takahashi and aoki, and output the larger one. If they are equal, output Draw.

Complexity

• Time complexity: \(O(N)\) — simply processing gems one by one in order
• Space complexity: \(O(N)\) — for storing the input array (can be reduced to \(O(1)\) with stream processing)

Implementation Notes

• Since the maximum value of \(K\) is \(10^{15}\), the maximum value of \(A_i\) is \(10^9\), and \(N\) is at most \(2 \times 10^5\), the total can be approximately \(2 \times 10^{14}\) at most. In C++ and similar languages, you need to use long long, but in Python there is no need to worry about integer overflow.

• Takahashi’s decision is “whether adding the current gem to the current total stays at most \(K\),” and note that this decision is made each time a gem is examined. No optimization or reordering is performed at all.

  Source Code

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

takahashi = 0
aoki = 0

for a in A:
    if takahashi + a <= K:
        takahashi += a
    else:
        aoki += a

if takahashi > aoki:
    print("Takahashi")
elif takahashi < aoki:
    print("Aoki")
else:
    print("Draw")

This editorial was generated by claude4.6opus-thinking.