Eating Candies

Moderate

0/80

0 upvote

Problem statement

Alice and Bob are eating a row of n candies. The size of the i-th candy is given by a_i. Alice eats from the left, and Bob eats from the right.

The game unfolds in alternating moves, with Alice starting first.

Move 1 (Alice): Alice eats exactly one candy from the left.
Subsequent Moves: On their turn, a player must eat one or more candies from their side such that the total size of candies eaten in their current move is strictly greater than the total size eaten by the opponent in their previous move. They should eat the minimum number of candies required to satisfy this condition.
Game End: If a player cannot meet the "strictly greater" condition, they eat all remaining candies on their side, and the game immediately ends.

Your task is to simulate the game and report the total number of moves, the total size of candies eaten by Alice, and the total size of candies eaten by Bob.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer T, the number of test cases.

For each test case:
  The first line contains an integer n, the number of candies.
  The second line contains n space-separated integers, representing the sizes of the candies.

Output Format:

For each test case, your function should return the total moves, Alice's total, and Bob's total. The runner code will handle printing these three values on a single line, separated by spaces.

Sample Input 1:

1
11
3 1 4 1 5 9 2 6 5 3 5

Sample Output 1:

6 23 21

Explanation for Sample 1:

Move 1 (Alice): Eats [3]. Sum=3. Alice's total=3.
Move 2 (Bob): Needs >3. Eats [5]. Sum=5. Bob's total=5.
Move 3 (Alice): Needs >5. Eats [1, 4, 1]. Sum=6. Alice's total=3+6=9.
Move 4 (Bob): Needs >6. Eats [3, 5]. Sum=8. Bob's total=5+8=13.
Move 5 (Alice): Needs >8. Eats [5, 9]. Sum=14. Alice's total=9+14=23.
Move 6 (Bob): Needs >14. Not enough candies. Eats remaining [2, 6]. Sum=8. Bob's total=13+8=21. Game ends.
Total Moves: 6. Alice's Total: 23. Bob's Total: 21.

Sample Input 2:

1
3
1 1 1

Sample Output 2:

2 1 2

Explanation for Sample 2:

Move 1 (Alice): Eats [1]. Sum=1. Alice's total=1.
Move 2 (Bob): Needs >1. Eats [1, 1]. Sum=2. Bob's total=2. Game ends as no candies are left.
Total Moves: 2. Alice's Total: 1. Bob's Total: 2.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= T <= 5000
1 <= n <= 1000
1 <= a_i <= 1000
The sum of n over all test cases does not exceed 2 * 10^5.

Approaches (1)

Approach 1

Two Pointers

Time Complexity

Space Complexity

(100% EXP penalty)

Eating Candies

Console