#CF2266B. Three Piles

Three Piles

题目描述

Alice 和 Bob 正在用三堆石子玩游戏。初始时,Alice 有 $a$ 颗石子,Bob 有 $b$ 颗石子,第三堆有 $c$ 颗石子。

Alice 和 Bob 轮流操作,Alice 先手。每回合,当前玩家可以从第三堆中取任意数量的石子(可以取零颗),并加入自己的堆中。

如果双方连续两回合都取零颗石子,游戏结束。

设 $A$ 和 $B$ 分别为游戏结束时 Alice 和 Bob 拥有的石子数。游戏得分为 $|A-B|$。

Alice 希望最大化得分,而 Bob 希望最小化得分。假设双方都采取最优策略,求最终得分。

输入格式

第一行包含一个整数 $t$($1 \le t \le 10^4$)— 测试数据组数。

每组测试数据包含三个整数 $a$、$b$、$c$($0 \le a,b,c \le 10^9$)— 分别表示 Alice 初始拥有的石子数、Bob 初始拥有的石子数以及第三堆的石子数。

输出格式

对于每组测试数据,输出一个整数 — 双方都采取最优策略时的最终得分。

请务必使用 $64$ 位整数类型,例如 C++ 中的 long long。

样例

5
3 6 3
3 6 10
5 5 4
2 5 6
67676767 41414141 998244353
3
7
4
3
1024506979

说明

在第一组测试数据中,Alice 可以在第一回合选择取 $0$ 颗石子。随后 Bob 也可以取 $0$ 颗石子,游戏以堆大小 $3$ 和 $6$ 结束。因此得分可以为 $3$。可以证明 Alice 无法获得更大的得分,Bob 也无法获得更小的得分。

在第二组测试数据中,Alice 可以在第一回合从第三堆取走全部 $10$ 颗石子。游戏以堆大小 $13$ 和 $6$ 结束,因此得分为 $7$。

来源

Imported from Codeforces — Codeforces Round 1122 (Div. 3).