{"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 *decimal* representation with her calculator.\n\nUnfortunately, 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.\n\nYour task is to help Ayu to determine the minimum number of bits to be removed from $S$ to satisfy Ayu's need.\n\nFor 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).\n\nInput 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.\n\nOutput contains an integer in a line representing the minimum number of bits to be removed from $S$.\n\n_Explanation for the sample input/output #1_\n\nThis sample is illustrated by the example given in the problem description above.\n\n_Explanation for the sample input/output #2_\n\nAyu must remove $4$ bits to get _111_, which is $7$ in its decimal representation.\n\n## Input\n\nInput 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.\n\n## Output\n\nOutput contains an integer in a line representing the minimum number of bits to be removed from $S$.\n\n[samples]\n\n## Note\n\n_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.","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 where $ v_i \\in \\{0\\} \\cup \\{1, 2, \\dots, n\\} $, with $ v_1 = 1 $ and at least one $ v_i = 0 $.  \n- A **valid sequence** $ D = (d_1, d_2, \\dots, d_n) $ satisfies:  \n  1. $ d_i = v_i $ for all $ v_i > 0 $.  \n  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.  \n  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 $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 4096 $  \n2. $ 2 \\leq n \\leq 10^5 $  \n3. $ v_1 = 1 $, $ v_i \\in [0, n] $, at least one $ v_i = 0 $  \n4. The sum of $ n $ over all test cases $ \\leq 6 \\times 10^6 $  \n5. At least one valid completion exists.  \n\n**Objective**  \nFor 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:  \n- The value $ k $,  \n- A valid sequence $ D = (d_1, \\dots, d_n) $ satisfying all constraints.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10200L","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}