D. Dog Show

Codeforces

IDCF847D

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsdata structuresgreedy

English · Original

Chinese · Translation

Formal · Original

A new dog show on TV is starting next week. On the show dogs are required to demonstrate bottomless stomach, strategic thinking and self-preservation instinct. You and your dog are invited to compete with other participants and naturally you want to win! On the show a dog needs to eat as many bowls of dog food as possible (bottomless stomach helps here). Dogs compete separately of each other and the rules are as follows: At the start of the show the dog and the bowls are located on a line. The dog starts at position _x_ = 0 and _n_ bowls are located at positions _x_ = 1, _x_ = 2, ..., _x_ = _n_. The bowls are numbered from 1 to _n_ from left to right. After the show starts the dog immediately begins to run to the right to the first bowl. The food inside bowls is not ready for eating at the start because it is too hot (dog's self-preservation instinct prevents eating). More formally, the dog can eat from the _i_\-th bowl after _t__i_ seconds from the start of the show or later. It takes dog 1 second to move from the position _x_ to the position _x_ + 1. The dog is not allowed to move to the left, the dog runs only to the right with the constant speed 1 distance unit per second. When the dog reaches a bowl (say, the bowl _i_), the following cases are possible: * the food had cooled down (i.e. it passed at least _t__i_ seconds from the show start): the dog immediately eats the food and runs to the right without any stop, * the food is hot (i.e. it passed less than _t__i_ seconds from the show start): the dog has two options: to wait for the _i_\-th bowl, eat the food and continue to run at the moment _t__i_ or to skip the _i_\-th bowl and continue to run to the right without any stop. After _T_ seconds from the start the show ends. If the dog reaches a bowl of food at moment _T_ the dog can not eat it. The show stops before _T_ seconds if the dog had run to the right of the last bowl. You need to help your dog create a strategy with which the maximum possible number of bowls of food will be eaten in _T_ seconds. ## Input Two integer numbers are given in the first line - _n_ and _T_ (1 ≤ _n_ ≤ 200 000, 1 ≤ _T_ ≤ 2·109) — the number of bowls of food and the time when the dog is stopped. On the next line numbers _t_1, _t_2, ..., _t__n_ (1 ≤ _t__i_ ≤ 109) are given, where _t__i_ is the moment of time when the _i_\-th bowl of food is ready for eating. ## Output Output a single integer — the maximum number of bowls of food the dog will be able to eat in _T_ seconds. [samples] ## Note In the first example the dog should skip the second bowl to eat from the two bowls (the first and the third).

下周将播出一场新的狗狗秀。在节目中，狗狗需要展示无底胃、战略思维和自我保护本能。你和你的狗狗将与其他参赛者竞争，当然你希望获胜！在节目中，狗狗需要尽可能多地吃掉狗粮碗（无底胃在这里有帮助）。狗狗各自独立比赛，规则如下：比赛开始时，狗狗和碗都位于一条直线上。狗狗从位置 #cf_span[x = 0] 出发，#cf_span[n] 个碗位于位置 #cf_span[x = 1, x = 2, ..., x = n]。碗从左到右编号为 #cf_span[1] 到 #cf_span[n]。比赛开始后，狗狗立即向右奔跑，前往第一个碗。碗中的食物在开始时太热而无法食用（狗狗的自我保护本能阻止它进食）。更正式地说，狗狗只有在比赛开始后至少 #cf_span[ti] 秒才能食用第 #cf_span[i] 个碗中的食物。狗狗从位置 #cf_span[x] 移动到位置 #cf_span[x + 1] 需要 1 秒。狗狗不允许向左移动，只能以每秒 1 个单位距离的恒定速度向右奔跑。当狗狗到达一个碗（例如第 #cf_span[i] 个碗）时，可能发生以下情况：比赛在 #cf_span[T] 秒后结束。如果狗狗在时刻 #cf_span[T] 到达某个碗，则无法食用该碗中的食物。如果狗狗在到达最后一个碗之后继续向右奔跑，则比赛会在 #cf_span[T] 秒之前停止。你需要帮助你的狗狗制定一个策略，使其在 #cf_span[T] 秒内吃掉尽可能多的碗。第一行给出两个整数 #cf_span[n] 和 #cf_span[T]（#cf_span[1 ≤ n ≤ 200 000]，#cf_span[1 ≤ T ≤ 2·109]）——分别表示狗粮碗的数量和狗狗停止的时间。下一行给出 #cf_span[n] 个整数 #cf_span[t1, t2, ..., tn]（#cf_span[1 ≤ ti ≤ 109]），其中 #cf_span[ti] 表示第 #cf_span[i] 个碗的食物在何时准备好被食用。请输出一个整数——狗狗在 #cf_span[T] 秒内最多能吃掉的碗的数量。在第一个例子中，狗狗应跳过第二个碗，以吃掉两个碗（第一个和第三个）。 ## Input 第一行给出两个整数 #cf_span[n] 和 #cf_span[T]（#cf_span[1 ≤ n ≤ 200 000]，#cf_span[1 ≤ T ≤ 2·109]）——分别表示狗粮碗的数量和狗狗停止的时间。下一行给出 #cf_span[n] 个整数 #cf_span[t1, t2, ..., tn]（#cf_span[1 ≤ ti ≤ 109]），其中 #cf_span[ti] 表示第 #cf_span[i] 个碗的食物在何时准备好被食用。 ## Output 请输出一个整数——狗狗在 #cf_span[T] 秒内最多能吃掉的碗的数量。 [samples] ## Note 在第一个例子中，狗狗应跳过第二个碗，以吃掉两个碗（第一个和第三个）。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of bowls, $ T \in \mathbb{Z}^+ $ be the total time limit. Let $ t_i \in \mathbb{Z}^+ $ for $ i \in \{1, \dots, n\} $ denote the earliest time at which bowl $ i $ (located at position $ i $) becomes edible. **Constraints** 1. $ 1 \leq n \leq 200{,}000 $ 2. $ 1 \leq T \leq 2 \cdot 10^9 $ 3. $ 1 \leq t_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Maximize the number of bowls $ k $ that the dog can eat under the following rules: - The dog starts at position $ 0 $ at time $ 0 $. - The dog moves right at speed $ 1 $ unit per second. - The dog reaches bowl $ i $ at time $ i $. - The dog may eat bowl $ i $ only if $ i \geq t_i $ (i.e., arrival time $ \geq $ readiness time). - The dog must stop at time $ T $; it cannot eat a bowl reached at time $ T $ or later. - The dog cannot move left. Find the maximum $ k $ such that there exists a strictly increasing sequence of indices $ i_1 < i_2 < \dots < i_k $ with: $$ i_j \geq t_{i_j} \quad \text{and} \quad i_j < T \quad \text{for all } j \in \{1, \dots, k\} $$ and the total time constraint is implicitly satisfied by the condition $ i_j < T $, since the dog arrives at bowl $ i_j $ at time $ i_j $. Thus, the problem reduces to: **Select the maximum number of bowls $ i \in \{1, \dots, n\} $ such that $ i < T $ and $ i \geq t_i $.**

Samples

Input #1

3 5
1 5 3

Output #1

Input #2

1 2
1

Output #2

Input #3

1 1
1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Dog Show",
    "description": {
      "content": "A new dog show on TV is starting next week. On the show dogs are required to demonstrate bottomless stomach, strategic thinking and self-preservation instinct. You and your dog are invited to compete ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF847D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A new dog show on TV is starting next week. On the show dogs are required to demonstrate bottomless stomach, strategic thinking and self-preservation instinct. You and your dog are invited to compete ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "下周将播出一场新的狗狗秀。在节目中，狗狗需要展示无底胃、战略思维和自我保护本能。你和你的狗狗将与其他参赛者竞争，当然你希望获胜！\n\n在节目中，狗狗需要尽可能多地吃掉狗粮碗（无底胃在这里有帮助）。狗狗各自独立比赛，规则如下：\n\n比赛开始时，狗狗和碗都位于一条直线上。狗狗从位置 #cf_span[x = 0] 出发，#cf_span[n] 个碗位于位置 #cf_span[x = 1, x = 2, ....",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of bowls, $ T \\in \\mathbb{Z}^+ $ be the total time limit.  \nLet $ t_i \\in \\mathbb{Z}^+ $ for $ i \\in \\{1, \\dots, n\\} $ denote the earliest ti...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments