3671. 唐纳德先生与领土扩张

单点时限: 6.0 sec

内存限制: 1024 MB

在一个一维的世界里,有 座城池。相邻的城池(也就是 座城市)如果属于同一个国家,他们就连成一个城邦。于是这 座城池连成了 个城邦。在发生战争时,城邦的大小是决定成败的最关键因素。

唐纳德先生与你各坐拥这个世界的一部分城池,你们经历了数千年的战争在形成了现在的局面。很不幸的是,从现在开始,你们的命运就不在自己手中了。有一个观察者,早就厌烦了这个世界里大大小小的持续了几千年的战争,他决定启用高维力量,一劳永逸地解决战乱。

于是他制定了以下规则:对于观察者来说,每一秒,唐纳德先生手下的城邦会同时在他们的右边界上发起进攻;你手下的城邦会在左边界上发起进攻。这就会产生战争。战争的成败取决于城邦的所占的城池多少,城邦大者赢;如果一样大,唐纳德先生会赢。(是的,这很不公平。)赢的一方可以在边界线上进一步,也就是说吃掉对方的一个城池。如果这是对方的城邦的最后一个城池,那么这个城邦就会消失,可能会有城邦与城邦会连成新的城邦。从而,在若干秒后,整个世界的格局就再也不会改变了。也就再也不会有战争。

听起来很完美?现在我想提前知道结果:要多少秒后格局才会定下来?到那时,唐纳德和你所拥有的城池数量各是多少?

输入格式

第一行一个整数 (),表示有 组测试数据。

对于每组数据,第一行是一个正整数 (),和一个字符 CD,分别表示目前有多少个城邦,以及最左边的城邦是属于你 (C) 还是唐纳德先生 (D)。

第二行有 个正整数用空格隔开 (, ),表示从左往右的城邦大小。如果最左边的城邦是 C,那么 对应 C, 对应 D, 对应 C,以此类推;如果最左边的城邦是 D,那么 对应 D,以此类推。

保证所有测试数据的 之和不超过

输出格式

对于每组测试数据,输出一行三个整数,分别为:所需的时间,唐纳德先生的城池数量,你的城池数量。

样例

Input
5
2 D
2 3
2 D
3 3
2 C
4 3
4 D
2 1 2 3
1 D
9
Output
2 0 5
3 6 0
0 3 4
5 8 0
0 9 0

提示

样例分别为:DDCCCDDDCCCCCCCDDDDDCDDCCCDDDDDDDDD

以第四个样例为例,其收敛经历了下述过程:DDCDDCCCDDDDCCCCDDDDDCCCDDDDDDCCDDDDDDDCDDDDDDDD

4 人解决,28 人已尝试。

5 份提交通过,共有 72 份提交。

9.2 EMB 奖励。

创建: 7 月,1 周前.

修改: 7 月,1 周前.

最后提交: 5 月,1 周前.

来源: EOJ Monthly 2019.1

题目标签