问题 H: 分糖果

问题 H: 分糖果

时间限制: 1 Sec  内存限制: 128 MB
提交: 509  解决: 274
[状态] [讨论版] [提交] [命题人:]
题目描述

爱丽丝和鲍勃已经收到了三大堆糖果作为礼物。现在,他们希望将这些糖果尽可能公平地分配。为此,爱丽丝拿了一堆糖果,然后鲍勃拿了另堆糖果。最后一堆糖果需要在爱丽丝鲍勃之间分配(可以全给一个人)

从糖果堆中取出糖果后,如果爱丽丝的糖果比鲍勃的糖果多,她会丢弃一些糖果,以使她拥有的糖果数量等于鲍勃的糖果数量。当然,如果鲍勃有更多的糖果,他也会这样做。

爱丽丝和鲍勃都希望获得尽可能多的糖果,他们在计划划分糖果的过程。请计算此划分过程之后,爱丽丝可以拥有的最大糖果数量(当然,鲍勃将拥有相同数量的糖果)。

例如三堆糖果数量分别是1,3,4,爱丽丝可以选择数量为1的一堆,鲍勃选择数量为3的一堆,然后爱丽丝从第三堆拿3个,鲍勃拿剩下的1个,这样他们都有4个糖果了。

另一个例子是三堆糖果数量分别是1,10,100,爱丽丝可以选择数量为1的一堆,鲍勃选择数量为10的一堆,然后爱丽丝从第三堆拿54个,鲍勃拿剩下46个,此时爱丽丝55个糖果,鲍勃56个糖果,鲍勃必须扔掉一个保证两人糖果数量都是55个。

输入

多实例,输入包含两行。

第一行一个整数t,表示有t组数据, 1<=t<=1000

第二行三个整数x,y,z,分别是三堆糖果的数量, 1<=x,y,z<=100000

输出

输出包含t行,每行表示本组数据下两人最后拥有的糖果数量。

样例输入 Copy
3
1 3 4
1 10 100
23 34 45
样例输出 Copy
4
55
51