B. Frodo and pillows

Codeforces

IDCF760B

Time1000ms

Memory256MB

Difficulty—

binary searchgreedy

English · Original

Chinese · Translation

Formal · Original

_n_ hobbits are planning to spend the night at Frodo's house. Frodo has _n_ beds standing in a row and _m_ pillows (_n_ ≤ _m_). Each hobbit needs a bed and at least one pillow to sleep, however, everyone wants as many pillows as possible. Of course, it's not always possible to share pillows equally, but any hobbit gets hurt if he has at least two pillows less than some of his neighbors have. Frodo will sleep on the _k_\-th bed in the row. What is the maximum number of pillows he can have so that every hobbit has at least one pillow, every pillow is given to some hobbit and no one is hurt? ## Input The only line contain three integers _n_, _m_ and _k_ (1 ≤ _n_ ≤ _m_ ≤ 109, 1 ≤ _k_ ≤ _n_) — the number of hobbits, the number of pillows and the number of Frodo's bed. ## Output Print single integer — the maximum number of pillows Frodo can have so that no one is hurt. [samples] ## Note In the first example Frodo can have at most two pillows. In this case, he can give two pillows to the hobbit on the first bed, and one pillow to each of the hobbits on the third and the fourth beds. In the second example Frodo can take at most four pillows, giving three pillows to each of the others. In the third example Frodo can take three pillows, giving two pillows to the hobbit in the middle and one pillow to the hobbit on the third bed.

#cf_span[n] 个霍比特人计划在弗罗多家过夜。弗罗多家有 #cf_span[n] 张床排成一行，以及 #cf_span[m] 个枕头（#cf_span[n ≤ m]）。每个霍比特人需要一张床和至少一个枕头才能睡觉，但每个人都希望拥有尽可能多的枕头。当然，枕头不可能平均分配，但如果某个霍比特人的枕头数比至少一个邻居少至少两个，他就会感到受伤。弗罗多将睡在第 #cf_span[k] 张床上。在保证每个霍比特人都至少有一个枕头、所有枕头都被分配、且无人受伤的前提下，弗罗多最多能拥有多少个枕头？输入仅一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ m ≤ 109], #cf_span[1 ≤ k ≤ n]）——分别表示霍比特人的数量、枕头的数量和弗罗多的床的编号。请输出一个整数——在无人受伤的前提下，弗罗多最多能拥有的枕头数量。在第一个例子中，弗罗多最多可以拥有两个枕头。此时，他可以给第一张床上的霍比特人两个枕头，给第三和第四张床上的霍比特人各一个枕头。在第二个例子中，弗罗多最多可以拿四个枕头，其余每个人各得三个枕头。在第三个例子中，弗罗多可以拿三个枕头，给中间的霍比特人两个枕头，给第三张床上的霍比特人一个枕头。 ## Input 输入仅一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ m ≤ 109], #cf_span[1 ≤ k ≤ n]）——分别表示霍比特人的数量、枕头的数量和弗罗多的床的编号。 ## Output 请输出一个整数——在无人受伤的前提下，弗罗多最多能拥有的枕头数量。 [samples] ## Note 在第一个例子中，弗罗多最多可以拥有两个枕头。此时，他可以给第一张床上的霍比特人两个枕头，给第三和第四张床上的霍比特人各一个枕头。在第二个例子中，弗罗多最多可以拿四个枕头，其余每个人各得三个枕头。在第三个例子中，弗罗多可以拿三个枕头，给中间的霍比特人两个枕头，给第三张床上的霍比特人一个枕头。

**Definitions** Let $ n, m, k \in \mathbb{Z}^+ $ with $ 1 \leq n \leq m \leq 10^9 $ and $ 1 \leq k \leq n $. Let $ x \in \mathbb{Z}^+ $ be the number of pillows Frodo (on bed $ k $) receives. Let $ a_i \in \mathbb{Z}^+ $ be the number of pillows given to the hobbit on bed $ i $, for $ i = 1, \dots, n $. **Constraints** 1. $ \sum_{i=1}^n a_i = m $ 2. $ a_i \geq 1 $ for all $ i \in \{1, \dots, n\} $ 3. $ |a_i - a_{i+1}| \leq 1 $ for all $ i \in \{1, \dots, n-1\} $ 4. $ a_k = x $ (Frodo’s pillow count) **Objective** Maximize $ x $ such that there exists a sequence $ (a_1, \dots, a_n) $ satisfying the above constraints.

Samples

Input #1

4 6 2

Output #1

Input #2

3 10 3

Output #2

Input #3

3 6 1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Frodo and pillows",
    "description": {
      "content": "_n_ hobbits are planning to spend the night at Frodo's house. Frodo has _n_ beds standing in a row and _m_ pillows (_n_ ≤ _m_). Each hobbit needs a bed and at least one pillow to sleep, however, every",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF760B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_n_ hobbits are planning to spend the night at Frodo's house. Frodo has _n_ beds standing in a row and _m_ pillows (_n_ ≤ _m_). Each hobbit needs a bed and at least one pillow to sleep, however, every...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "#cf_span[n] 个霍比特人计划在弗罗多家过夜。弗罗多家有 #cf_span[n] 张床排成一行，以及 #cf_span[m] 个枕头（#cf_span[n ≤ m]）。每个霍比特人需要一张床和至少一个枕头才能睡觉，但每个人都希望拥有尽可能多的枕头。当然，枕头不可能平均分配，但如果某个霍比特人的枕头数比至少一个邻居少至少两个，他就会感到受伤。\n\n弗罗多将睡在第 #cf_span[k] 张床上...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq m \\leq 10^9 $ and $ 1 \\leq k \\leq n $.  \nLet $ x \\in \\mathbb{Z}^+ $ be the number of pillows Frodo (on bed $ k $) receives.  \nLe...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments