A. Frames

Codeforces

IDCF93A

Time2000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Throughout Igor K.'s life he has had many situations worthy of attention. We remember the story with the virus, the story of his mathematical career and of course, his famous programming achievements. However, one does not always adopt new hobbies, one can quit something as well. This time Igor K. got disappointed in one of his hobbies: editing and voicing videos. Moreover, he got disappointed in it so much, that he decided to destroy his secret archive for good. Igor K. use Pindows XR operation system which represents files and folders by small icons. At that, _m_ icons can fit in a horizontal row in any window. Igor K.'s computer contains _n_ folders in the D: disk's root catalog. The folders are numbered from 1 to _n_ in the order from the left to the right and from top to bottom (see the images). At that the folders with secret videos have numbers from _a_ to _b_ inclusive. Igor K. wants to delete them forever, at that making as few frame selections as possible, and then pressing Shift+Delete exactly once. What is the minimum number of times Igor K. will have to select the folder in order to select folders from _a_ to _b_ and only them? Let us note that if some selected folder is selected repeatedly, then it is deselected. Each selection possesses the shape of some rectangle with sides parallel to the screen's borders. ## Input The only line contains four integers _n_, _m_, _a_, _b_ (1 ≤ _n_, _m_ ≤ 109, 1 ≤ _a_ ≤ _b_ ≤ _n_). They are the number of folders in Igor K.'s computer, the width of a window and the numbers of the first and the last folders that need to be deleted. ## Output Print a single number: the least possible number of times Igor K. will have to select the folders using frames to select only the folders with numbers from _a_ to _b_. [samples] ## Note The images below illustrate statement tests. The first test: ![image](https://espresso.codeforces.com/4cf387edb795a636603e2e49bfbcaadb4774ffdc.png) In this test we can select folders 3 and 4 with out first selection, folders 5, 6, 7, 8 with our second selection and folder 9 with our third, last selection. The second test: ![image](https://espresso.codeforces.com/5b127f6da5847287832ba9301652cd63f39a4968.png) In this test we can first select all folders in the first row (2, 3, 4, 5), then — all other ones.

在 Igor K. 的一生中，他经历过许多值得铭记的时刻。我们还记得他与病毒的故事、他的数学生涯，当然还有他著名的编程成就。然而，人并不总是在不断尝试新爱好，有时也需要放弃某些东西。这一次，Igor K. 对他的一项爱好感到失望：视频剪辑与配音。他对此失望至极，决定彻底销毁他的秘密档案。 Igor K. 使用 Pindows XR 操作系统，该系统用小图标表示文件和文件夹。在任意窗口中，一行最多可容纳 #cf_span[m] 个图标。 Igor K. 的计算机 D: 盘根目录下有 #cf_span[n] 个文件夹，这些文件夹按从左到右、从上到下的顺序编号为 #cf_span[1] 到 #cf_span[n]（见图示）。其中，包含秘密视频的文件夹编号为从 #cf_span[a] 到 #cf_span[b]（包含两端）。Igor K. 希望永久删除这些文件夹，且希望尽可能少地进行框选操作，然后一次性按下 Shift+Delete。请问，Igor K. 最少需要多少次框选操作，才能仅选中编号从 #cf_span[a] 到 #cf_span[b] 的所有文件夹？注意，如果某个文件夹被重复选中，则会被取消选中。每次框选操作的形状必须是边与屏幕边框平行的矩形。仅一行包含四个整数 #cf_span[n], #cf_span[m], #cf_span[a], #cf_span[b]（#cf_span[1 ≤ n, m ≤ 109]，#cf_span[1 ≤ a ≤ b ≤ n]），分别表示 Igor K. 计算机中的文件夹总数、窗口宽度，以及需要删除的首个和末尾文件夹编号。输出一个整数：Igor K. 最少需要多少次框选操作，才能仅选中编号从 #cf_span[a] 到 #cf_span[b] 的所有文件夹。下图展示了题面中的测试用例。第一个测试用例：在本测试中，我们可以第一次选中文件夹 3 和 4，第二次选中文件夹 5、6、7、8，第三次选中文件夹 9。第二个测试用例：在本测试中，我们可以先选中第一行的所有文件夹（2、3、4、5），再选中其余所有文件夹。 ## Input 仅一行包含四个整数 #cf_span[n], #cf_span[m], #cf_span[a], #cf_span[b]（#cf_span[1 ≤ n, m ≤ 109]，#cf_span[1 ≤ a ≤ b ≤ n]），分别表示 Igor K. 计算机中的文件夹总数、窗口宽度，以及需要删除的首个和末尾文件夹编号。 ## Output 输出一个整数：Igor K. 最少需要多少次框选操作，才能仅选中编号从 #cf_span[a] 到 #cf_span[b] 的所有文件夹。 [samples] ## Note 下图展示了题面中的测试用例。第一个测试用例：在本测试中，我们可以第一次选中文件夹 3 和 4，第二次选中文件夹 5、6、7、8，第三次选中文件夹 9。第二个测试用例：在本测试中，我们可以先选中第一行的所有文件夹（2、3、4、5），再选中其余所有文件夹。

**Definitions** Let $ n, m, a, b \in \mathbb{Z}^+ $ with $ 1 \leq a \leq b \leq n $ and $ 1 \leq m \leq 10^9 $. The folders are arranged in a grid with $ m $ icons per row, numbered left-to-right, top-to-bottom from $ 1 $ to $ n $. A selection is a rectangular region with sides parallel to the grid axes. **Constraints** - $ 1 \leq n, m \leq 10^9 $ - $ 1 \leq a \leq b \leq n $ **Objective** Find the minimum number of rectangular selections required to select exactly the contiguous set of folders $ \{a, a+1, \dots, b\} $, where selecting a folder twice toggles its selection state (on/off), and only the target range may be selected after all operations.

Samples

Input #1

11 4 3 9

Output #1

Input #2

20 5 2 20

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Frames",
    "description": {
      "content": "Throughout Igor K.'s life he has had many situations worthy of attention. We remember the story with the virus, the story of his mathematical career and of course, his famous programming achievements.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF93A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Throughout Igor K.'s life he has had many situations worthy of attention. We remember the story with the virus, the story of his mathematical career and of course, his famous programming achievements....",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在 Igor K. 的一生中，他经历过许多值得铭记的时刻。我们还记得他与病毒的故事、他的数学生涯，当然还有他著名的编程成就。然而，人并不总是在不断尝试新爱好，有时也需要放弃某些东西。\n\n这一次，Igor K. 对他的一项爱好感到失望：视频剪辑与配音。他对此失望至极，决定彻底销毁他的秘密档案。\n\nIgor K. 使用 Pindows XR 操作系统，该系统用小图标表示文件和文件夹。在任意窗口中，一行...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m, a, b \\in \\mathbb{Z}^+ $ with $ 1 \\leq a \\leq b \\leq n $ and $ 1 \\leq m \\leq 10^9 $.  \nThe folders are arranged in a grid with $ m $ icons per row, numbered left-to-right,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments