← 返回题目列表

Codeforces · 93/A

A. 框架

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

在 Igor K. 的一生中,他遇到过许多值得关注的情况。我们记得病毒的故事、他的数学生涯的故事,当然还有他著名的编程成就。然而,一个人并不总是会养成新的爱好,一个人也可以放弃某些东西。

这次 Igor K. 对他的一项爱好感到失望:视频编辑和配音。此外,他对此非常失望,以至于他决定永远销毁他的秘密档案。

Igor K. 使用 Pindows XR 操作系统,通过小图标表示文件和文件夹。这样,m 个图标就可以适合任何窗口中的水平行。

Igor K. 的计算机在 D: 盘根目录下包含 n 个文件夹。这些文件夹按照从左到右、从上到下的顺序从 1 到 n 编号(参见图像)。此时,包含秘密视频的文件夹的编号为从 a 到 b(含)。 Igor K. 想要永久删除它们,即尽可能少地选择帧,然后按 Shift+Delete 一次。 Igor K. 必须选择该文件夹的最少次数是多少次才能选择从 a 到 b 的文件夹并且仅选择它们?请注意,如果重复选择某个选定的文件夹,则会取消选择该文件夹。每个选择都具有某种矩形的形状,其边与屏幕边框平行。

输入

唯一一行包含四个整数 n, m, a, b (1 ≤ n, m ≤ 109, 1 ≤ a ≤ b ≤ n)。它们是Igor K. 计算机中的文件夹数量、窗口宽度以及需要删除的第一个和最后一个文件夹的数量。

输出

打印单个数字:Igor K. 必须使用框架选择文件夹的尽可能少的次数,以仅选择编号为 a 到 b 的文件夹。

示例

输入 #1

11 4 3 9

输出 #1

3

输入 #2

20 5 2 20

输出 #2

2

注意

下图说明了语句测试。

第一次测试:

在此测试中,我们可以选择文件夹 3 和 4(无需第一次选择),文件夹 5、6、7、8(第二次选择)和文件夹 9(第三次、最后一次选择)。

第二次测试:

在此测试中,我们可以首先选择第一行中的所有文件夹(2、3、4、5),然后选择所有其他文件夹。