← 返回题目列表

Codeforces · 2228/B

B. 蕾米莉亚玩 Soku

中文机器翻译题面 查看原题

蕾米莉亚试图逃跑,而灵梦则想要进行最后一击。

比赛场地包括 $$$n$$$ 位置排列成圆圈。对于每个 $$$1 \le i \lt n$$$,仓位 $$$i$$$ 和 $$$i+1$$$ 相邻,并且位置 $$$1$$$ 和 $$$n$$$ 也相邻。

最初,在时间 $$$0$$$,灵梦在位置 $$$x_1$$$ 并且 Remilia 位于位置 $$$x_2$$$,其中 $$$x_1 \ne x_2$$$。

每一秒,都会按顺序发生以下情况:

  1. 蕾米莉亚要么移动到相邻位置,要么留在原地。在整个游戏中,她最多可以移动到相邻位置 $$$k$$$ 次。
  2. 观察蕾米莉亚的动作后,灵梦要么移动到相邻位置,要么留在原地。
  3. 如果两次行动后他们处于同一位置,灵梦抓住蕾米莉亚,游戏结束。

假设两名玩家都发挥最佳状态,灵梦总是尝试最小化接球时间,而蕾米莉亚则尝试最大化它。

找出灵梦抓住蕾米莉亚之前的秒数。

输入

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

每个测试用例的唯一行包含四个整数 $$$n$$$, $$$x_1$$$, $$$x_2$$$ 和 $$$k$$$ ($$$2\le n\le10^8$$$, $$$1\le x_1,x_2\le n$$$, $$$x_1\ne x_2$$$, $$$0\le k\le 10^8$$$)。

输出

对于每个测试用例,假设两个玩家都处于最佳状态,输出灵梦抓住雷米莉亚之前的秒数。

示例

输入
复制

4
2 1 2 0
4 3 2 1
4 2 3 1
16 8 4 2

输出
复制

1
2
2
6

注意

在第一个测试用例中,一个可能的操作顺序是:

  • 第一秒,蕾米莉亚原地不动,然后灵梦移动到 $$$2$$$ 并抓住了雷米莉亚。

在第二个测试用例中,一个可能的操作顺序是:

  • 第一秒,蕾米莉亚移动到 $$$1$$$,然后灵梦移动到 $$$2$$$.
  • 第二秒,蕾米莉亚无法移动,只能原地不动,然后灵梦移动到 $$$1$$$ 并抓住了雷米莉亚。