Overview

As \(N\) gems flow by in order, Takahashi secures gems according to a specific rule (he takes a gem as long as his total does not exceed \(K\)), and the remaining gems go to Aoki. The problem asks us to compare their final total values.

Analysis

The key point of this problem is that “Takahashi’s decision on whether to take a gem depends only on his cumulative total value up to that point.”

Since the gems flow on a conveyor belt, their order cannot be changed. Therefore, the problem can be solved by simulating the process from the beginning, determining one by one whether Takahashi can take each gem.

Points to Consider

• Constraint sizes: The number of gems \(N\) is at most \(2 \times 10^5\), the threshold \(K\) is at most \(10^{15}\), and each gem’s value \(A_i\) is at most \(10^9\).
• Data types: The total value can be as large as approximately \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\). In Python, there is no limitation on integer size, so this is not an issue, but in other languages (such as C++), you need to use a 64-bit integer type (such as long long).
• Computational complexity: An \(O(N)\) algorithm that checks each of the \(N\) elements once is well within the time limit.

Algorithm

We perform the simulation with the following steps:

1. Initialize Takahashi’s total value takahashi_sum and Aoki’s total value aoki_sum to \(0\).
2. Process the gem values \(A_1, A_2, \ldots, A_N\) in order, repeating the following:
   • If takahashi_sum + A_i is at most \(K\), Takahashi takes that gem.
     • Add \(A_i\) to takahashi_sum.
   • Otherwise, Aoki takes that gem.
     • Add \(A_i\) to aoki_sum.
3. After processing all gems, compare takahashi_sum and aoki_sum:
   • If takahashi_sum > aoki_sum, output Takahashi.
   • If aoki_sum > takahashi_sum, output Aoki.
   • If they are equal, output Draw.

Complexity

• Time complexity: \(O(N)\)
  • Since we only scan the list of gems once, the computation finishes in time proportional to the number of gems \(N\).
• Space complexity: \(O(N)\)
  • If we store the input gem values in a list, we use memory proportional to \(N\).

Implementation Tips

• Fast input: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Conditional branching: The rule “do not take a gem if it would cause the total to exceed \(K\)” should be accurately expressed with the condition if takahashi_sum + val <= k:.

  Source Code

import sys

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N と K を取得
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 宝石の価値のリストを取得
    a = map(int, input_data[2:])
    
    takahashi_sum = 0
    aoki_sum = 0
    
    # ルールに従って宝石を分配する
    for val in a:
        if takahashi_sum + val <= k:
            # 高橋君が取った合計が K 以下なら高橋君が取る
            takahashi_sum += val
        else:
            # そうでなければ青木君が取る
            aoki_sum += val
            
    # 結果を判定して出力
    if takahashi_sum > aoki_sum:
        print("Takahashi")
    elif aoki_sum > takahashi_sum:
        print("Aoki")
    else:
        print("Draw")

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.