外传:home_w和seventh的博弈游戏

TimeLimit:1000MS  MemoryLimit:32MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

有一天,home_w和seventh在玩石子游戏,规则是这样的:有n堆石子,每堆石子个数为ai。他们从第1堆开始按顺序选择到第n堆,seventh先手,当轮到某个人时,有两种操作:

  1. 若这个人选择将这堆石子归入囊中,那么下一轮主动权交给对方

  2. 这个人可以将这堆石子给对方,那么下一轮主动权还是归自己

他们两人都很聪明,都采取最优策略让自己能得到的石子尽可能多,请问他们最后分别能得到多少个石子。

Input

第一行输入一个t,表示有t组数据。

接下来t组数据,先输入一个n,表示有n堆石子,然后n个正整数ai,表示第 i 堆石子的个数。

保证n的和不超过100000,1<=ai<=100000,保证每组数据的石子总数在int范围内。

Output

输出 t 行,每行两个数,分别表示home_w和seventh的最后得分。

SampleInput
1
5
10 21 10 21 10
SampleOutput
31 41

Hint:
第一轮:seventh选择将第一堆给home_w,下一轮还是由seventh选择,此时 10:0
第二轮:seventh选择拿走第二堆,下一轮变为由home_w选择,此时 10:21
第三轮:home_w选择将第三堆给seventh,下一轮还是由自己选择,此时 10:31
第四轮:home_w选择拿走第四堆,下一轮变为seventh选择,此时 31:31
第五轮:seventh拿走第五堆,游戏结束 31:41
Submit
题目统计信息详细
总AC数24
通过人数14
尝试人数16
总提交量57
AC率24.56%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签
作者
Satan666

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: