L. Binary String

Codeforces

IDCF10200L

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

A binary string is a non-empty sequence of $0$'s and $1$'s, e.g., _010110_, _1_, _11101_, etc. Ayu has a favorite binary string $S$ which contains no leading zeroes. She wants to convert $S$ into its *decimal* representation with her calculator. Unfortunately, her calculator cannot work on any integer larger than $K$ and it will crash. Therefore, Ayu may need to remove zero or more bits from $S$ while maintaining the order of the remaining bits such that its decimal representation is no larger than $K$. The resulting binary string also must not contain any leading zeroes. Your task is to help Ayu to determine the minimum number of bits to be removed from $S$ to satisfy Ayu's need. For example, let $S$ = _1100101_ and $K = 13$. Note that _1100101_ is $101$ in decimal representation, thus, we need to remove several bits from $S$ to make it no larger than $K$. We can remove the $3^(r d)$, $5^(t h)$, and $6^(t h)$ most significant bits, i.e. _1100101_ $arrow.r$ _1101_. The decimal representation of _1101_ is $13$, which is no larger than $K = 13$. In this example, we removed $3$ bits, and this is the minimum possible (If we remove only $2$ bits, then we will have a binary string of length $5$ bits; notice that any binary string of length $5$ bits has a value of at least $16$ in decimal representation). Input begins with a line containing an integer $K$ ($1 <= K <= 2^(60)$) representing the limit of Ayu's calculator. The second line contains a binary string $S$ ($1 <= | S | <= 60$) representing Ayu's favorite binary string. You may safely assume $S$ contains no leading zeroes. Output contains an integer in a line representing the minimum number of bits to be removed from $S$. _Explanation for the sample input/output #1_ This sample is illustrated by the example given in the problem description above. _Explanation for the sample input/output #2_ Ayu must remove $4$ bits to get _111_, which is $7$ in its decimal representation. ## Input Input begins with a line containing an integer $K$ ($1 <= K <= 2^(60)$) representing the limit of Ayu's calculator. The second line contains a binary string $S$ ($1 <= | S | <= 60$) representing Ayu's favorite binary string. You may safely assume $S$ contains no leading zeroes. ## Output Output contains an integer in a line representing the minimum number of bits to be removed from $S$. [samples] ## Note _Explanation for the sample input/output #1_This sample is illustrated by the example given in the problem description above._Explanation for the sample input/output #2_Ayu must remove $4$ bits to get _111_, which is $7$ in its decimal representation.

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case: - Let $ n \in \mathbb{Z} $ be the number of days. - Let $ V = (v_1, v_2, \dots, v_n) $ be a sequence where $ v_i \in \{0\} \cup \{1, 2, \dots, n\} $, with $ v_1 = 1 $ and at least one $ v_i = 0 $. - A **valid sequence** $ D = (d_1, d_2, \dots, d_n) $ satisfies: 1. $ d_i = v_i $ for all $ v_i > 0 $. 2. There exists a strictly increasing sequence of days $ 1 = d^{(1)} < d^{(2)} < \dots < d^{(k)} \leq n $ such that on day $ d^{(j)} $, Mr. Light learns meal $ j $ for the first time. 3. For all days $ t \in [d^{(j)}, d^{(j+1)} - 1] $, the meal cooked on day $ t $ is $ ((t - d^{(j)}) \bmod j) + 1 $. **Constraints** 1. $ 1 \leq T \leq 4096 $ 2. $ 2 \leq n \leq 10^5 $ 3. $ v_1 = 1 $, $ v_i \in [0, n] $, at least one $ v_i = 0 $ 4. The sum of $ n $ over all test cases $ \leq 6 \times 10^6 $ 5. At least one valid completion exists. **Objective** For each test case, find the **minimum** $ k \in \mathbb{Z}^+ $ such that there exists a valid sequence $ D $ with exactly $ k $ distinct meals learned, and output: - The value $ k $, - A valid sequence $ D = (d_1, \dots, d_n) $ satisfying all constraints.

API Response (JSON)

{
  "problem": {
    "name": "L. Binary String",
    "description": {
      "content": "A binary string is a non-empty sequence of $0$'s and $1$'s, e.g., _010110_, _1_, _11101_, etc. Ayu has a favorite binary string $S$ which contains no leading zeroes. She wants to convert $S$ into its ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10200L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A binary string is a non-empty sequence of $0$'s and $1$'s, e.g., _010110_, _1_, _11101_, etc. Ayu has a favorite binary string $S$ which contains no leading zeroes. She wants to convert $S$ into its ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the number of days.  \n- Let $ V = (v_1, v_2, \\dots, v_n) $ be a sequence w...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments