C. War Strategy

时间限制：每次测试 2 秒
内存限制：每次测试 256 兆字节

问题描述

战争爆发了！作为国家的最高将领，你必须制定部署军队的策略。

一条直线上有 $n$ 个基地，其中第 $k$ 个基地是你军队的大本营。最初，基地 $k$ 只有一名士兵。

每一天，按顺序发生以下事情： 1. 你发布一条命令：选择一个基地 $i$ ( $1 \le i \le n$ )，并选择该基地内的任意数量的士兵（可以选择 $0$ 个或当前该基地内的所有士兵）。然后，命令所有你选中的士兵移动到基地 $i-1$ 或基地 $i+1$ 。所有士兵必须朝同一方向移动，并且任何士兵不允许移动到基地 $1$ 的左边或基地 $n$ 的右边。 2. 然后，一名新士兵加入并移动到基地 $k$ 。这名士兵不能被当天的命令所指挥。

然而，时间紧迫，距离敌人进攻只剩 $m$ 天了。如果一个基地至少有一名士兵驻守，则称其为设防基地。你的任务是找出在第 $m$ 天结束时，你所能拥有的设防基地的最大数量（包括本垒基地）。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 10^4$ )。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $n$ , $m$ , $k$ ( $1 \le k \le n \le 10^5$ , $1 \le m \le 10^9$ ) —— 分别表示基地的数量、你用于强化基地的天数以及本垒基地的索引。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出在第 $m$ 天结束时你所能拥有的最大设防基地数量。

样例输入

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

样例输出

样例说明

在第二个测试用例中，有一种方法可以强化 $3$ 个基地： - 第一天，命令基地 $3$ 中的 $0$ 名士兵移动到基地 $2$ 。在一天结束时，一名新士兵移动到基地 $2$ （现在基地 $2$ 有 $2$ 名士兵，其他基地有 $0$ 名士兵）。 - 第二天，命令基地 $2$ 中的 $1$ 名士兵移动到基地 $1$ 。在一天结束时，一名新士兵移动到基地 $2$ 。现在基地 $2$ 有 $2$ 名士兵，基地 $1$ 有 $1$ 名士兵。 - 第三天，命令基地 $2$ 中的 $2$ 名士兵移动到基地 $3$ 。在一天结束时，一名新士兵移动到基地 $2$ 。现在基地 $1$ 有 $1$ 名士兵，基地 $2$ 有 $2$ 名士兵，基地 $3$ 有 $2$ 名士兵。现在，基地 $1$ ， $2$ ， $3$ 都至少有一名士兵。因此，答案是 $3$ 。

在第三个测试用例中，你可以通过以下方式实现强化 $3$ 个基地： - 第一天，命令现有的士兵从基地 $2$ 移动到基地 $3$ 。在一天结束时，一名新士兵移动到基地 $2$ 。 - 第二天，命令基地 $2$ 中的士兵移动到基地 $1$ 。在一天结束时，一名新士兵移动到基地 $2$ 。现在，基地 $1$ , $2$ , $3$ 都有一名士兵。因此，答案是 $3$ 。可以证明，在第 $2$ 天结束时，我们不可能拥有超过 $3$ 个设防基地。

下方是对第三个测试用例的一个生动解释。（译者注：原文此处提及一个解释，但未提供具体内容，故保留说明。） ![[Pasted image 20260107230635.png]]