思维1217A · Creating a Character20 分
你又一次玩你最喜欢的游戏。你选择了一个你以前没玩过的角色。它有 str 点力量和 int 点智力。此外，在开始时，角色有 exp 点自由经验点，你可以将其投资于力量或智力（通过投资一点，你可以将力量提高 1 或将智力提高 1）。
由于你想制造一些乐趣，你想创建一个运动员角色，因此它的力量点数多于智力点数（最终力量严格大于最终智力）。
计算你可以创建的不同角色构建数量（为了可重玩性），如果你必须投资所有自由点数。两个角色构建不同，如果它们的力量和/或智力不同。
输入 / 输出 / 样例（含数据范围）· 不写代码可以跳过
输入
第一行包含单个整数 T（1 ≤ T ≤ 100）——查询数量。接下来的 T 行包含查询描述——每行一个。
这一行包含三个整数 str、int 和 exp（1 ≤ str, int ≤ 10^8，0 ≤ exp ≤ 10^8）——角色的初始力量和智力以及自由点数。
输出
打印 T 个整数——每个查询一个。对于每个查询，打印你可以创建的不同角色构建数量。
样例
输入
4
5 3 4
2 1 0
3 5 5
4 10 6
输出
3
1
2
0
提示
在第一个查询中，只有三种合适的角色构建：(str = 7, int = 5)、(8, 4) 和 (9, 3)。所有其他构建要么太聪明，要么没有使用所有自由点数。
在第二个查询中，只有一种可能的构建：(2, 1)。
在第三个查询中，有两种合适的构建：(7, 6)、(8, 5)。
在第四个查询中，所有构建都太聪明了。
提示
难度 1300 · binary search, math
标答
关键结论：设给力量分配 x 点（0≤x≤exp），则最终力量 str+x，智力 int+exp-x。条件 str+x > int+exp-x 即 2x > int+exp-str，令 d = int+exp-str。x 需满足 x > d/2 且 0≤x≤exp，故 x 的下界为 max(0, floor(d/2)+1)，答案 = max(0, exp - max(0, floor(d/2)+1) + 1)。
参考代码：
for each query:
d = int + exp - str
lo = max(0, d//2 + 1) // 注意 d 可能为负，Python 整除需小心，可用 (d+1)//2 或分情况
ans = max(0, exp - lo + 1)
print(ans)
更稳妥写法：
lo = 0
if d >= 0: lo = d//2 + 1
ans = max(0, exp - lo + 1)
构造909B · Segments
给定一个整数 N。考虑坐标轴上所有可能的线段，其端点为整数点，坐标在 0 到 N 之间（含 0 和 N）；这样的线段共有 (N+1)N/2 条。
你想把这些线段分成若干层来画，使得每一层中的线段互不重叠（不过它们可以在端点处相接）。你不能把线段移动到坐标轴上的其他位置。
求对于给定的 N，所需的最少层数。
输入 / 输出 / 样例（含数据范围）· 不写代码可以跳过
输入
输入仅一行，包含一个整数 N（1 ≤ N ≤ 100）。
输出
输出一个整数——对于给定的 N，绘制这些线段所需的最少层数。
样例
输入
2
输出
2
输入
3
输出
4
输入
4
输出
6
提示
作为示例，下面是 N = 4 时的线段及其最优分层方案。
提示
难度 1300 · constructive algorithms, math