E. Karen and Neighborhood

Codeforces

IDCF815E

Time2000ms

Memory512MB

Difficulty—

binary searchconstructive algorithmsimplementation

English · Original

Chinese · Translation

Formal · Original

It's been long after the events of the previous problems, and Karen has now moved on from student life and is looking to relocate to a new neighborhood. <center>![image](https://espresso.codeforces.com/98a21e268909f1f46465e8399ed702a46eb6858e.png)</center>The neighborhood consists of _n_ houses in a straight line, labelled 1 to _n_ from left to right, all an equal distance apart. Everyone in this neighborhood loves peace and quiet. Because of this, whenever a new person moves into the neighborhood, he or she always chooses the house whose minimum distance to any occupied house is maximized. If there are multiple houses with the maximum possible minimum distance, he or she chooses the leftmost one. Note that the first person to arrive always moves into house 1. Karen is the _k_\-th person to enter this neighborhood. If everyone, including herself, follows this rule, which house will she move into? ## Input The first and only line of input contains two integers, _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 1018), describing the number of houses in the neighborhood, and that Karen was the _k_\-th person to move in, respectively. ## Output Output a single integer on a line by itself, the label of the house Karen will move into. [samples] ## Note In the first test case, there are 6 houses in the neighborhood, and Karen is the fourth person to move in: 1. The first person moves into house 1. 2. The second person moves into house 6. 3. The third person moves into house 3. 4. The fourth person moves into house 2. In the second test case, there are 39 houses in the neighborhood, and Karen is the third person to move in: 1. The first person moves into house 1. 2. The second person moves into house 39. 3. The third person moves into house 20.

在之前的题目事件之后很久，Karen 已经离开了学生生活，正打算搬进一个新社区。这个社区由一条直线上的 #cf_span[n] 栋房子组成，从左到右编号为 #cf_span[1] 到 #cf_span[n]，每栋房子之间的距离相等。社区里的每个人都热爱和平与宁静。因此，每当有新人搬入时，他/她总是选择与任何已入住房子的最小距离最大的房子。如果有多个房子具有相同的最大最小距离，则选择最左边的那个。注意，第一个搬入的人总是住进第 #cf_span[1] 栋房子。 Karen 是第 #cf_span[k] 个搬入这个社区的人。如果包括她在内的所有人都遵循这一规则，她会搬进哪一栋房子？输入仅有一行，包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 1018]），分别表示社区中的房子数量以及 Karen 是第 #cf_span[k] 个搬入的人。 ## Input 输入仅有一行，包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 1018]），分别表示社区中的房子数量以及 Karen 是第 #cf_span[k] 个搬入的人。 ## Output 请输出一个单独的整数，表示 Karen 将搬入的房子编号。 [samples] ## Note 在第一个测试用例中，社区中有 #cf_span[6] 栋房子，Karen 是第四位搬入的人：第一位搬入者住进第 #cf_span[1] 栋房子。第二位搬入者住进第 #cf_span[6] 栋房子。第三位搬入者住进第 #cf_span[3] 栋房子。第四位搬入者（Karen）住进第 #cf_span[2] 栋房子。在第二个测试用例中，社区中有 #cf_span[39] 栋房子，Karen 是第三位搬入的人：第一位搬入者住进第 #cf_span[1] 栋房子。第二位搬入者住进第 #cf_span[39] 栋房子。第三位搬入者（Karen）住进第 #cf_span[20] 栋房子。

**Definitions** Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq k \leq n \leq 10^{18} $. Let $ H = \{1, 2, \dots, n\} $ be the set of house labels. Let $ S_m \subseteq H $ be the set of occupied houses after the $ m $-th person moves in, with $ S_1 = \{1\} $. **Constraints** For each $ m \in \{2, \dots, k\} $, the $ m $-th person chooses house $ h_m \in H \setminus S_{m-1} $ such that: $$ h_m = \arg\max_{h \in H \setminus S_{m-1}} \left( \min_{s \in S_{m-1}} |h - s| \right) $$ and if multiple such $ h $ exist, choose the smallest one. **Objective** Find $ h_k $, the house chosen by the $ k $-th person.

Samples

Input #1

6 4

Output #1

Input #2

39 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Karen and Neighborhood",
    "description": {
      "content": "It's been long after the events of the previous problems, and Karen has now moved on from student life and is looking to relocate to a new neighborhood. <center>![image](https://espresso.codeforces.c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF815E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "It's been long after the events of the previous problems, and Karen has now moved on from student life and is looking to relocate to a new neighborhood.\n\n<center>![image](https://espresso.codeforces.c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在之前的题目事件之后很久，Karen 已经离开了学生生活，正打算搬进一个新社区。\n\n这个社区由一条直线上的 #cf_span[n] 栋房子组成，从左到右编号为 #cf_span[1] 到 #cf_span[n]，每栋房子之间的距离相等。\n\n社区里的每个人都热爱和平与宁静。因此，每当有新人搬入时，他/她总是选择与任何已入住房子的最小距离最大的房子。如果有多个房子具有相同的最大最小距离，则选择最左边的...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 10^{18} $.  \nLet $ H = \\{1, 2, \\dots, n\\} $ be the set of house labels.  \nLet $ S_m \\subseteq H $ be the set of occupied hou...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments