← 返回题目列表

Codeforces · 1352/D

D. 爱丽丝、鲍勃和糖果

中文机器翻译题面 查看原题

一排有$$$n$$$糖果,它们从左到右编号为$$$1$$$到$$$n$$$。第 $$$i$$$ 糖果的大小为 $$$a_i$$$。

爱丽丝和鲍勃玩了一个有趣又美味的游戏:他们吃糖果。爱丽丝将从左到右吃糖果,鲍勃从右到左吃糖果。如果所有糖果都被吃掉,游戏结束。

该过程由移动组成。在移动过程中,玩家从她/他的一侧吃一颗或多颗糖果(爱丽丝从左边吃,鲍勃从右边吃)。

Alice 迈出了第一步。在第一步中,她会吃$$$1$$$糖果(其大小为$$$a_1$$$)。然后,玩家交替进行每个连续的移动——也就是说,鲍勃进行第二步,然后是爱丽丝,然后是鲍勃,依此类推。

在每次移动中,玩家都会计算当前移动期间吃掉的糖果的总大小。一旦这个数字严格大于其他玩家在上一步中吃掉的糖果的总大小,当前玩家就会停止吃东西并且移动结束。换句话说,在一次移动中,玩家吃掉尽可能少的糖果,使得在该移动中吃掉的糖果的大小总和严格大于另一玩家在上一步中吃掉的糖果大小的总和。如果没有足够的糖果以这种方式移动,则玩家吃掉所有剩余的糖果,游戏结束。

例如,如果 $$$n=11$$$ 且 $$$a=[3,1,4,1,5,9,2,6,5,3,5]$$$,则:

- 第 1 步:爱丽丝吃了一颗 $$$3$$$ 大小的糖果,糖果序列变为 $$$[1,4,1,5,9,2,6,5,3,5]$$$。
- 第 2 步:Alice 在上一步中吃了 $$$3$$$,这意味着 Bob 必须吃 $$$4$$$ 或更多。鲍勃吃了一颗 $$$5$$$ 大小的糖果,糖果序列变为 $$$[1,4,1,5,9,2,6,5,3]$$$。
- 第 3 步:Bob 在上一步中吃了 $$$5$$$,这意味着 Alice 必须吃 $$$6$$$ 或更多。爱丽丝吃了三颗糖果,总大小为$$$1+4+1=6$$$,糖果的序列变为$$$[5,9,2,6,5,3]$$$。
- 第 4 步:Alice 在上一步中吃了 $$$6$$$,这意味着 Bob 必须吃 $$$7$$$ 或更多。鲍勃吃了两颗糖果,总大小为$$$3+5=8$$$,糖果的序列变为$$$[5,9,2,6]$$$。
- 第 5 步:Bob 在上一步中吃了 $$$8$$$,这意味着 Alice 必须吃 $$$9$$$ 或更多。爱丽丝吃了两颗糖果,总大小为$$$5+9=14$$$,糖果的序列变为$$$[2,6]$$$。
- 第 6 步(最后一步):Alice 在上一步中吃了 $$$14$$$,这意味着 Bob 必须吃 $$$15$$$ 或更多。这是不可能的,所以鲍勃吃掉了剩下的两颗糖果,游戏结束。

打印游戏中的步数和两个数字:

- $$$a$$$ — 爱丽丝在游戏过程中吃掉的所有糖果的总大小;
- $$$b$$$ — 鲍勃在游戏期间吃掉的所有糖果的总大小。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 输入中测试用例的数量。以下是 $$$t$$$ 测试用例的描述。

每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 糖果的数量。第二行包含整数序列 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — 糖果的大小按照从左到右排列的顺序排列。

保证测试中所有输入数据集的 $$$n$$$ 值之和不超过 $$$2\cdot10^5$$$。

输出

对于每组输入数据,打印三个整数 - 游戏中的移动次数以及所需的值 $$$a$$$ 和 $$$b$$$。

示例

输入 #1

7
11
3 1 4 1 5 9 2 6 5 3 5
1
1000
3
1 1 1
13
1 2 3 4 5 6 7 8 9 10 11 12 13
2
2 1
6
1 1 1 1 1 1
7
1 1 1 1 1 1 1

输出 #1

6 23 21
1 1000 0
2 1 2
6 45 46
2 2 1
3 4 2
4 4 3