#P2218. 筹码对弈

筹码对弈

本题需要文件读写

文件 IO 为:输入文件 chips.in,输出文件 chips.out。请使用上述文件名读入和输出。

问题描述

科技节设置了一项筹码对弈活动。小林和小周面前各有一堆筹码,分别包含 aa 枚和 bb 枚;桌面中央还有一堆公共筹码,共 cc 枚。

两人轮流行动,小林先行动。每次行动时,当前玩家可以从公共筹码中取出任意枚筹码,加入自己的一堆,也可以取 00 枚。取出的数量不能超过公共筹码当前的数量。

如果连续两次行动都取了 00 枚筹码,活动结束。公共筹码即使尚未取完,也可以按这一规则结束活动。

设活动结束时,小林和小周分别拥有 AA 枚、BB 枚筹码,活动的得分为 ∣A−B∣|A-B|。小林希望这个得分尽可能大,小周希望这个得分尽可能小。

假设两人都采取最优策略,求最后的得分。

输入格式

第一行包含一个正整数 TT,表示测试用例数。本题固定 T=10T=10。

接下来 TT 行,每行包含三个整数 a,b,ca,b,c,分别表示小林、小周和公共筹码的初始数量。

输出格式

对于每个测试用例,输出一行一个整数,表示最后的得分。

样例输入 1

10
3 6 3
3 6 10
5 5 4
2 5 6
67676767 41414141 998244353
0 0 0
0 8 0
7 0 5
0 6 12
0 6 13

样例输出 1

3
7
4
3
1024506979
0
8
12
6
7

说明

公开分档大样例:下载 samples.zip。

评测数据规模

对于 100%100\% 的数据,保证 T=10T=10,0≤a,b,c≤1090\le a,b,c\le10^9,所有输入均为整数。

各测试点的附加限制如下表所示:

测试点编号 a,b≤a,b\le c≤c\le 特殊性质
1∼41\sim4 88 无
5∼85\sim8 10910^9 A
9∼129\sim12 B
13∼1613\sim16 C
17∼2017\sim20 无
  • 特殊性质 A:c=0c=0。
  • 特殊性质 B:a=ba=b。
  • 特殊性质 C:a≥ba\ge b。

本题共 2020 个独立测试点,每点 55 分。