Shoot the birds !
There are n birds in a row, they are numbered from left to right from 1 to n. The weight of
the i-th bird is Wi.
The hunters named Albert and Binnie play an interesting game: they shoot these birds.
Albert will shoot birds from left to right, and Binnie — from right to left. The game ends if all
the birds are shot.
The process consists of moves. During a move, the player shoots one or more birds from
her/his side (Albert shoots from the left, Binnie — from the right).
Albert makes the first move. During the first move, he will shoot 1 bird (its weight is W1).
Then, each successive move the players alternate — that is, Binnie makes the second
move, then Albert, then again Binnie and so on.
On each move, a player counts the total weight of birds shot during the current move. Once
this number becomes strictly greater than the total weight of birds shot by the other player
on their previous move, the current player stops shooting and the move ends. In other
words, on a move, a player shoots the smallest possible number of birds such that the sum
of the weights of birds shot on this move is strictly greater than the sum of the weights of
birds that the other player shot on the previous move. If there are not enough birds to make
a move this way, then the player shoots all the remaining birds and the game ends.
For example, if n=11 and W=[3,1,4,1,5,9,2,6,5,3,5], then:
move 1: Albert shoots one bird of weight 3 and the sequence of birds becomes
[1,4,1,5,9,2,6,5,3,5].
move 2: Albert shot 3 on the previous move, which means Binnie must shoot 4 or more.
Binnie shoots one bird of weight 5 and the sequence of birds becomes [1,4,1,5,9,2,6,5,3].
move 3: Binnie shot 5 on the previous move, which means Albert must shoot 6 or more.
Albert shoots three birds with the total weight of 1+4+1=6 and the sequence of birds
becomes [5,9,2,6,5,3].
move 4: Albert shot 6 on the previous move, which means Binnie must shoot 7 or more.
Binnie shoots two birds with the total weight of 3+5=8 and the sequence of birds becomes
[5,9,2,6].
move 5: Binnie shot 8 on the previous move, which means Albert must shoot 9 or more.
Albert shoots two birds with the total weight of 5+9=14 and the sequence of birds becomes
[2,6].
move 6 (the last): Albert shot 14 on the previous move, which means Binnie must shoot 15
or more. It is impossible, so Binnie shoots the two remaining birds and the game ends.
Print the number of moves in the game and two numbers:
a — the total weight of all birds shot by Albert during the game;
b — .the total weight of all birds shot by Binnie during the game;
INPUT:
- The first line contains an integer T — the number of test cases in the input. The
following are descriptions of the T test cases.
- Each test case consists of two lines. The first line contains an integer n— the number
of birds. The second line contains a sequence of integers W1,W2,…,Wn — the weight
of birds in the order they are arranged from left to right.
- It is guaranteed that the sum of the values of n for all sets of input data in a test does
not exceed 2*105.
OUTPUT:
- For each set of input data print three space separated integers — the number of
moves in the game and the required values a and b.
CONSTRAINTS :
● 1 <= T <= 5000
● 1 <= n, Wi <= 100
- Time limit per test = 1 sec
- Source Limit = 50 MBytes
- I/O = Standard I/O
SAMPLE INPUTS :
- Test #1
3
11
31415926535
1
1000
7
2222222
SAMPLE OUTPUTS :
- Test #1
6 23 21
1 1000 0
486