A16502 | $War Strategy$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

战争爆发了！你作为国家的最高将领，必须制定战略部署你的军队。 有 $n$ 个基地排成一行，第 $k$ 个基地是你的主基地。最开始，只有一个士兵驻扎在第 $k$ 个基地。每天按照如下顺序发生： - 你下达命令，选择一个基地 $i$（$1 \leq i \leq n$），并选择该基地内任意数量的士兵（可以为 $0$，也可以为该基地全部士兵），然后命令这些士兵全部向相同方向移动：要么移动到 $i-1$ 号基地，要么移动到 $i+1$ 号基地。没有士兵能够移动到 $1$ 号基地的左侧或 $n$ 号基地的右侧。 - 之后，会有一名新的士兵加入到第 $k$ 个基地。这名士兵不能被当天的命令调动。 不过时间紧迫，距离敌军进攻只剩下 $m$ 天。一个基地如果驻有至少一名士兵，则称之为被加固。你的任务是，在第 $m$ 天结束时，你最多能让多少个基地被加固（包括主基地）。

每个测试用例包含多组数据。第一行包含测试组数 $t$（$1 \le t \le 10^4$）。接下来描述每组数据。 每组数据的第一行包含三个整数 $n$、$m$、$k$（$1 \leq k \leq n \leq 10^5$，$1 \leq m \leq 10^9$），表示基地数量、你可以加固基地的天数，以及主基地的编号。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组数据，输出第 $m$ 天结束时你最多能加固的基地数量。

输入 #1

7
3 1 3
3 3 2
4 2 2
3 2 1
4 3 3
7 7 4
100000 1000000000 100000

输出 #1

C++ 编辑器

输入

输出