Overview

This is a problem where Takahashi and Aoki distribute gems in order, and the winner is determined by comparing their final total values. Takahashi keeps taking gems as long as his total remains at most \(K\), and Aoki takes all the gems that Takahashi doesn’t take.

Analysis

This problem follows a simple rule where Takahashi’s actions are determined by the order in which the gems arrive. Takahashi keeps taking gems as long as his current total is at most \(K\), and if taking a gem would cause his total to exceed \(K\), he doesn’t take it, so Aoki takes it instead. The key point is that Takahashi’s actions are determined by a greedy approach. In other words, by simply repeating the optimal choice at each step (take the gem if the total stays at most \(K\)), we can compute the final total values for both players.

Algorithm

1. Initialize Takahashi’s total takahashi_sum and Aoki’s total aoki_sum to 0.
2. Process the gems in order:
   • If adding the next gem’s value to Takahashi’s current total keeps it at most \(K\), Takahashi takes that gem (add to takahashi_sum).
   • Otherwise, Takahashi does not take that gem, and Aoki takes it instead (add to aoki_sum).
3. After processing all gems, compare both totals:
   • If takahashi_sum > aoki_sum, Takahashi wins.
   • If takahashi_sum < aoki_sum, Aoki wins.
   • If they are equal, it’s a draw.

Complexity

• Time complexity: \(O(N)\)
  • Because we process each of the \(N\) gems exactly once.
• Space complexity: \(O(N)\)
  • Required for the array storing the gem values.

Implementation Notes

• For input reading, processing can be done efficiently by reading all the data at once.

• For each gem, a conditional branch determines whether Takahashi takes it or not.

• The comparison of totals is done with a simple magnitude comparison.

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    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 takahashi_sum < aoki_sum:
        print("Aoki")
    else:
        print("Draw")

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.