← 返回题目列表

Codeforces · 1196/A

A. 三堆糖果

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

Alice 和 Bob 收到了三大堆糖果作为礼物。现在他们想尽可能公平地分配这些糖果。为此,爱丽丝拿走一堆糖果,然后鲍勃拿走另外两堆糖果之一。最后一堆按照 Alice 和 Bob 的意愿分配:例如,Alice 可能拿走整堆,而 Bob 却什么也得不到。

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

Alice和Bob想要拥有尽可能多的糖果,他们相应地规划了分配糖果的过程。请计算出经过此划分过程后,Alice 最多可以拥有多少颗糖果(当然,Bob 也将拥有相同数量的糖果)。

您必须回答 $$$q$$$ 独立查询。

让我们看以下示例:$$$[1, 3, 4]$$$。然后爱丽丝可以选择第三堆,鲍勃可以拿第二堆,然后第一堆中唯一的糖果给鲍勃 - 那么爱丽丝有 $$$4$$$ 糖果,鲍勃有 $$$4$$$ 糖果。

另一个例子是$$$[1, 10, 100]$$$。那么Alice可以选择第二堆,Bob可以选择第一堆,第三堆糖果可以这样分配:Bob拿走$$$54$$$糖果,Alice拿走$$$46$$$糖果。现在鲍勃有 $$$55$$$ 糖果,爱丽丝有 $$$56$$$ 糖果,所以她必须丢弃一颗糖果 - 之后,她也有 $$$55$$$ 糖果。

输入

输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 1000$$$) — 查询数。然后是 $$$q$$$ 查询。

查询中唯一一行包含三个整数 $$$a、b$$$ 和 $$$c$$$ ($$$1 \le a, b, c \le 10^{16}$$$)——分别对应第一堆、第二堆和第三堆糖果的数量。

输出

打印 $$$q$$$ 行。第 $$$i$$$ 行应包含第 $$$i$$$ 查询的答案 - 如果爱丽丝和鲍勃都表现最佳,则爱丽丝在除法后可以拥有的最大糖果数量(当然,鲍勃将拥有相同数量的糖果)。

示例

输入 #1

4
1 3 4
1 10 100
10000000000000000 10000000000000000 10000000000000000
23 34 45

输出 #1

4
55
15000000000000000
51