L. Bars

Codeforces

IDCF795L

Time2000ms

Memory256MB

Difficulty—

binary searchgreedy

English · Original

Chinese · Translation

Formal · Original

Polycarp's workday lasts exactly $n$ minutes. He loves chocolate bars and can eat one bar in one minute. Today Polycarp has $k$ bars at the beginning of the workday. In some minutes of the workday Polycarp has important things to do and in such minutes he is not able to eat a chocolate bar. In other minutes he can either eat or not eat one chocolate bar. It is guaranteed, that in the first and in the last minutes of the workday Polycarp has no important things to do and he will always eat bars in this minutes to gladden himself at the begining and at the end of the workday. Also it is guaranteed, that $k$ is strictly greater than $1$. Your task is to determine such an order of eating chocolate bars that the maximum break time between eating bars is as minimum as possible. Consider that Polycarp eats a bar in the minute $x$ and the next bar in the minute $y$ ($x < y$). Then the break time is equal to $y - x - 1$ minutes. It is not necessary for Polycarp to eat all bars he has. ## Input The first line contains two integers $n$ and $k$ ($2 \le n \le 200\,000$, $2 \le k \le n$) — the length of the workday in minutes and the number of chocolate bars, which Polycarp has in the beginning of the workday. The second line contains the string with length $n$ consisting of zeros and ones. If the $i$\-th symbol in the string equals to zero, Polycarp has no important things to do in the minute $i$ and he can eat a chocolate bar. In the other case, Polycarp is busy in the minute $i$ and can not eat a chocolate bar. It is guaranteed, that the first and the last characters of the string are equal to zero, and Polycarp always eats chocolate bars in these minutes. ## Output Print the minimum possible break in minutes between eating chocolate bars. [samples] ## Note In the first example Polycarp can not eat the chocolate bar in the second minute, so the time of the break equals to one minute. In the second example Polycarp will eat bars in the minutes $1$ and $8$ anyway, also he needs to eat the chocolate bar in the minute $5$, so that the time of the maximum break will be equal to $3$ minutes.

Polycarp 的工作日持续恰好 $n$ 分钟。他喜欢巧克力棒，每分钟可以吃掉一根。今天 Polycarp 在工作日开始时有 $k$ 根巧克力棒。在工作日的某些分钟里，Polycarp 有重要的事情要做，在这些分钟里他无法吃巧克力棒。在其他分钟里，他可以选择吃或不吃一根巧克力棒。保证在工作日的第一分钟和最后一分钟，Polycarp 没有重要的事情要做，他一定会在这两个时间点吃巧克力棒，以在工作日开始和结束时让自己开心。同时保证 $k$ 严格大于 $1$。你的任务是确定一种吃巧克力棒的顺序，使得吃巧克力棒之间的最大间隔时间尽可能小。假设 Polycarp 在第 $x$ 分钟吃了一根巧克力棒，下一根在第 $y$ 分钟吃（$x < y$），则间隔时间为 $y - x - 1$ 分钟。Polycarp 不必吃掉他所有的巧克力棒。第一行包含两个整数 $n$ 和 $k$（$2 lt.eq n lt.eq 200 thin 000$，$2 lt.eq k lt.eq n$）——工作日的分钟数和 Polycarp 在工作日开始时拥有的巧克力棒数量。第二行包含一个长度为 $n$ 的由 0 和 1 组成的字符串。如果字符串的第 $i$ 个字符为 0，则 Polycarp 在第 $i$ 分钟没有重要的事情要做，可以吃一根巧克力棒；否则，他在第 $i$ 分钟很忙，无法吃巧克力棒。保证字符串的第一个和最后一个字符都是 0，且 Polycarp 总是在这两个时间点吃巧克力棒。 ## Input 第一行包含两个整数 $n$ 和 $k$（$2 lt.eq n lt.eq 200 thin 000$，$2 lt.eq k lt.eq n$）——工作日的分钟数和 Polycarp 在工作日开始时拥有的巧克力棒数量。第二行包含一个长度为 $n$ 的由 0 和 1 组成的字符串。如果字符串的第 $i$ 个字符为 0，则 Polycarp 在第 $i$ 分钟没有重要的事情要做，可以吃一根巧克力棒；否则，他在第 $i$ 分钟很忙，无法吃巧克力棒。保证字符串的第一个和最后一个字符都是 0，且 Polycarp 总是在这两个时间点吃巧克力棒。 ## Output 输出吃巧克力棒之间的最小可能的最大间隔时间（以分钟为单位）。 [samples] ## Note 在第一个例子中，Polycarp 无法在第二分钟吃巧克力棒，因此间隔时间为一分钟。在第二个例子中，Polycarp 必然会在第 1 分钟和第 8 分钟吃巧克力棒，并且他还需要在第 5 分钟吃一根巧克力棒，以使得最大间隔时间为 3 分钟。

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 2 \leq n \leq 200000 $, $ 2 \leq k \leq n $. Let $ s \in \{0,1\}^n $ be a binary string where $ s_i = 0 $ indicates minute $ i $ is free (can eat), $ s_i = 1 $ indicates minute $ i $ is busy (cannot eat). Let $ F \subseteq \{1, \dots, n\} $ be the set of free minutes: $ F = \{ i \mid s_i = 0 \} $. It is given that $ 1 \in F $, $ n \in F $, and Polycarp **must** eat at minutes $ 1 $ and $ n $. Let $ E \subseteq F $ be the set of minutes when Polycarp eats chocolate bars, with $ |E| = k $, $ 1, n \in E $. **Constraints** 1. $ E \subseteq F $, $ |E| = k $, $ \min(E) = 1 $, $ \max(E) = n $. 2. For any two consecutive eating times $ x, y \in E $ with $ x < y $ and no $ z \in E $ such that $ x < z < y $, the break time is $ y - x - 1 $. **Objective** Minimize the maximum break time between consecutive eating events: $$ \min_{\substack{E \subseteq F \\ |E| = k \\ 1,n \in E}} \max_{\substack{x,y \in E \\ y = \text{succ}_E(x)}} (y - x - 1) $$ where $ \text{succ}_E(x) $ denotes the next eating time after $ x $ in $ E $.

Samples

Input #1

3 3
010

Output #1

Input #2

8 3
01010110

Output #2

API Response (JSON)

{
  "problem": {
    "name": "L. Bars",
    "description": {
      "content": "Polycarp's workday lasts exactly $n$ minutes. He loves chocolate bars and can eat one bar in one minute. Today Polycarp has $k$ bars at the beginning of the workday. In some minutes of the workday Po",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF795L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp's workday lasts exactly $n$ minutes. He loves chocolate bars and can eat one bar in one minute. Today Polycarp has $k$ bars at the beginning of the workday.\n\nIn some minutes of the workday Po...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 的工作日持续恰好 $n$ 分钟。他喜欢巧克力棒，每分钟可以吃掉一根。今天 Polycarp 在工作日开始时有 $k$ 根巧克力棒。\n\n在工作日的某些分钟里，Polycarp 有重要的事情要做，在这些分钟里他无法吃巧克力棒。在其他分钟里，他可以选择吃或不吃一根巧克力棒。保证在工作日的第一分钟和最后一分钟，Polycarp 没有重要的事情要做，他一定会在这两个时间点吃巧克力棒，以在工...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 200000 $, $ 2 \\leq k \\leq n $.  \nLet $ s \\in \\{0,1\\}^n $ be a binary string where $ s_i = 0 $ indicates minute $ i $ is free (can eat...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments