J. Zero Game

Codeforces

IDCF10123J

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

You are given one string S consisting of only '_0_' and '_1_'. You are bored, so you start to play with the string. In each operation, you can move any character of this string to some other position in the string. For example, suppose . Then you can move the first zero to the tail, and S will become '_0100_'. Additionally, you have Q numbers K1, K2, ..., KQ. For each i, you wonder what can be the maximum number of consecutive zeroes in the string if you start with S and use at most Ki operations. In order to satisfy your curiosity, please write a program which will find the answers for you. The first line of input contains one string S. The second line of input contains one integer Q. Each of the following Q lines contains one integer Ki indicating the maximum number of operations in i-th query. For each query, output one line containing one number: the answer for this query. ## Input The first line of input contains one string S. The second line of input contains one integer Q. Each of the following Q lines contains one integer Ki indicating the maximum number of operations in i-th query. 2 ≤ N ≤ 106 the length of S is exactly N characters S consists of only '_0_' and '_1_' 1 ≤ Q ≤ 105 N × Q ≤ 2 × 107 1 ≤ Ki ≤ 106 ## Output For each query, output one line containing one number: the answer for this query. [samples]

**Definitions** Let $ S \in \{0,1\}^* $ be the input binary string. Let $ z = |S|_0 $ be the total number of '0's in $ S $. Let $ Q \in \mathbb{Z}^+ $ be the number of queries. For each query $ i \in \{1, \dots, Q\} $, let $ K_i \in \mathbb{Z}_{\geq 0} $ be the maximum allowed operations. **Constraints** Each operation consists of moving one character to any other position in $ S $. The total number of '0's $ z $ is invariant under operations. **Objective** For each query $ i $, find the maximum possible length $ L_i $ of a contiguous substring of '0's achievable in $ S $ using at most $ K_i $ operations. That is, $$ L_i = \max \left\{ \ell \in \mathbb{Z} \mid 0 \leq \ell \leq z \text{ and } \ell \text{ consecutive '0's can be formed with } \leq K_i \text{ moves} \right\} $$

API Response (JSON)

{
  "problem": {
    "name": "J. Zero Game",
    "description": {
      "content": "You are given one string S consisting of only '_0_' and '_1_'. You are bored, so you start to play with the string. In each operation, you can move any character of this string to some other position ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10123J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given one string S consisting of only '_0_' and '_1_'. You are bored, so you start to play with the string. In each operation, you can move any character of this string to some other position ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S \\in \\{0,1\\}^* $ be the input binary string.  \nLet $ z = |S|_0 $ be the total number of '0's in $ S $.  \nLet $ Q \\in \\mathbb{Z}^+ $ be the number of queries.  \nFor each query ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments