← 返回题目列表

Codeforces · 2109/B

B. 切片生存

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

决斗者 Mouf 和 Fouad 进入竞技场,这是一个 $$$n \times m$$$ 网格!

Fouad 的怪物从单元格 $$$(a, b)$$$ 开始,其中行编号为 $$$1$$$ 到 $$$n$$$,列编号为 $$$1$$$ 到 $$$m$$$。

Mouf 和 Fouad 将继续决斗,直到网格仅由一个单元格组成。

每回合:

  • Mouf首先沿着行或列线将网格切割成两部分,丢弃没有Fouad怪物的部分。请注意,网格必须至少有两个单元格;否则,游戏就已经结束了。
  • 之后,在同一回合中,福阿德将他的怪物移动到剩余网格内的任何单元格(可能是原来所在的单元格)。
第四个测试用例的各个阶段的可视化。

Mouf 希望最小化回合数,而 Fouad 希望最大化回合数。如果双方都发挥最佳,这场史诗般的对决会持续多少回合?

输入

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

每个测试用例的第一行也是唯一一行包含四个整数 $$$n$$$、$$$m$$$、$$$a$$$ 和 $$$b$$$ ($$$2 \le n, m \le 10^9$$$, $$$1 \le a \le n$$$, $$$1 \le b \le m$$$) — 表示行数、列、怪物的起始行和怪物的起始列。

输出

对于每个测试用例,输出一个整数 - 如果双方都发挥最佳状态,这场史诗般的决斗将持续的回合数。

示例

输入
复制

8
2 2 1 1
3 3 2 2
2 7 1 4
2 7 2 2
8 9 4 6
9 9 5 5
2 20 2 11
22 99 20 70

输出
复制

2
4
4
3
6
8
6
10

注意

在第一个测试用例中,一个可能的决斗序列如下:

  • 第 1 回合:Mouf 沿着 $$$1$$$ 行和 $$$2$$$ 行之间的线水平切割网格,删除下半部分并留下 $$$1 \times 2$$$ 网格。
  • 第 1 回合:Fouad 的怪物位于单元格 $$$(1,1)$$$ 处。
  • 第 2 回合:Mouf 再次切割 $$$1 \times 2$$$ 网格,删除一列,并隔离单元格 $$$(1,1)$$$。

决斗在 $$$2$$$ 回合内完成。

在第四种情况下,一种可能的决斗顺序如下:

  • 第 1 回合:Mouf 沿着 $$$2$$$ 和 $$$3$$$ 列之间的线垂直切割网格,将其分成 $$$2 \times 2$$$ 和 $$$2 \times 5$$$ 字段,然后删除 $$$2 \times 5$$$ 部分。
  • 第1回合:福阿德将怪物移至单元格$$$(1,1)$$$。
  • 从这一点开始,决斗就像第一个测试用例一样进行——另外两个回合将网格从 $$$2 \times 2$$$ 修剪到单个 $$$1 \times 1$$$ 单元格。

总共,决斗在 $$$3$$$ 回合内完成。

第四个测试用例的说明可以参考问题陈述中提到的图片。