A. Mister B and Book Reading

Codeforces

IDCF820A

Time2000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Mister B once received a gift: it was a book about aliens, which he started read immediately. This book had _c_ pages. At first day Mister B read _v_0 pages, but after that he started to speed up. Every day, starting from the second, he read _a_ pages more than on the previous day (at first day he read _v_0 pages, at second — _v_0 + _a_ pages, at third — _v_0 + 2_a_ pages, and so on). But Mister B is just a human, so he physically wasn't able to read more than _v_1 pages per day. Also, to refresh his memory, every day, starting from the second, Mister B had to reread last _l_ pages he read on the previous day. Mister B finished the book when he read the last page for the first time. Help Mister B to calculate how many days he needed to finish the book. ## Input First and only line contains five space-separated integers: _c_, _v_0, _v_1, _a_ and _l_ (1 ≤ _c_ ≤ 1000, 0 ≤ _l_ < _v_0 ≤ _v_1 ≤ 1000, 0 ≤ _a_ ≤ 1000) — the length of the book in pages, the initial reading speed, the maximum reading speed, the acceleration in reading speed and the number of pages for rereading. ## Output Print one integer — the number of days Mister B needed to finish the book. [samples] ## Note In the first sample test the book contains 5 pages, so Mister B read it right at the first day. In the second sample test at first day Mister B read pages number 1 - 4, at second day — 4 - 11, at third day — 11 - 12 and finished the book. In third sample test every day Mister B read 1 page of the book, so he finished in 15 days.

Mister B 曾收到一份礼物：一本关于外星人的书，他立即开始阅读。这本书共有 $c$ 页。第一天，Mister B 读了 $v0$ 页，但之后他开始加快速度。从第二天起，每天他比前一天多读 $a$ 页（第一天读 $v0$ 页，第二天读 $v0 + a$ 页，第三天读 $v0 + 2a$ 页，依此类推）。但 Mister B 只是普通人，因此他每天实际能读的页数最多不超过 $v1$ 页。此外，为了巩固记忆，从第二天起，Mister B 每天必须重读前一天读过的最后 $l$ 页。Mister B 在首次读到最后一页时完成了这本书。请帮助 Mister B 计算他需要多少天才能读完这本书。第一行且仅有一行包含五个空格分隔的整数：$c$、$v0$、$v1$、$a$ 和 $l$（$1 ≤ c ≤ 1000$，$0 ≤ l < v0 ≤ v1 ≤ 1000$，$0 ≤ a ≤ 1000$）——分别是书的页数、初始阅读速度、最大阅读速度、阅读速度的加速度以及重读页数。输出一个整数——Mister B 读完这本书所需的天数。在第一个样例中，书共有 $5$ 页，因此 Mister B 在第一天就读完了。在第二个样例中，第一天 Mister B 读了第 $1 - 4$ 页，第二天读了第 $4 - 11$ 页，第三天读了第 $11 - 12$ 页，从而完成了这本书。在第三个样例中，Mister B 每天读 $1$ 页，因此他在 15 天后完成。 ## Input 第一行且仅有一行包含五个空格分隔的整数：$c$、$v0$、$v1$、$a$ 和 $l$（$1 ≤ c ≤ 1000$，$0 ≤ l < v0 ≤ v1 ≤ 1000$，$0 ≤ a ≤ 1000$）——分别是书的页数、初始阅读速度、最大阅读速度、阅读速度的加速度以及重读页数。 ## Output 输出一个整数——Mister B 读完这本书所需的天数。 [samples] ## Note 在第一个样例中，书共有 $5$ 页，因此 Mister B 在第一天就读完了。在第二个样例中，第一天 Mister B 读了第 $1 - 4$ 页，第二天读了第 $4 - 11$ 页，第三天读了第 $11 - 12$ 页，从而完成了这本书。在第三个样例中，Mister B 每天读 $1$ 页，因此他在 15 天后完成。

**Definitions** Let $ c \in \mathbb{Z}^+ $ be the total number of pages in the book. Let $ v_0, v_1, a, l \in \mathbb{Z} $ be the initial reading speed, maximum reading speed, daily acceleration, and rereading pages, respectively, with constraints $ 1 \leq c \leq 1000 $, $ 0 \leq l < v_0 \leq v_1 \leq 1000 $, $ 0 \leq a \leq 1000 $. Let $ d \in \mathbb{Z}^+ $ be the number of days required to finish the book. Let $ p_i \in \mathbb{Z} $ be the number of **new** pages read on day $ i $. Let $ r_i \in \mathbb{Z} $ be the cumulative total of **distinct** pages read up to and including day $ i $. **Constraints** - On day 1: $ p_1 = v_0 $, $ r_1 = v_0 $. - For $ i \geq 2 $: - $ p_i = \min(v_0 + (i-1)a, v_1) $, - But Mister B must reread the last $ l $ pages from day $ i-1 $, so the **net new** pages added on day $ i $ is $ \max(0, p_i - l) $. - Thus: $ r_i = r_{i-1} + \max(0, p_i - l) $. **Objective** Find the smallest $ d $ such that $ r_d \geq c $.

Samples

Input #1

5 5 10 5 4

Output #1

Input #2

12 4 12 4 1

Output #2

Input #3

15 1 100 0 0

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Mister B and Book Reading",
    "description": {
      "content": "Mister B once received a gift: it was a book about aliens, which he started read immediately. This book had _c_ pages. At first day Mister B read _v_0 pages, but after that he started to speed up. Ev",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF820A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mister B once received a gift: it was a book about aliens, which he started read immediately. This book had _c_ pages.\n\nAt first day Mister B read _v_0 pages, but after that he started to speed up. Ev...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Mister B 曾收到一份礼物：一本关于外星人的书，他立即开始阅读。这本书共有 $c$ 页。\n\n第一天，Mister B 读了 $v0$ 页，但之后他开始加快速度。从第二天起，每天他比前一天多读 $a$ 页（第一天读 $v0$ 页，第二天读 $v0 + a$ 页，第三天读 $v0 + 2a$ 页，依此类推）。但 Mister B 只是普通人，因此他每天实际能读的页数最多不超过 $v1$ 页。\n\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ c \\in \\mathbb{Z}^+ $ be the total number of pages in the book.  \nLet $ v_0, v_1, a, l \\in \\mathbb{Z} $ be the initial reading speed, maximum reading speed, daily acceleration, ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments