{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"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."},{"iden":"output","content":"Output contains an integer in a line representing the minimum number of bits to be removed from $S$."},{"iden":"examples","content":"Input13\n1100101\nOutput3\nInput13\n1111111\nOutput4\n"},{"iden":"note","content":"_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."}],"translated_statement":[{"iden":"statement","content":"编程训练营将在伯兰举行。参赛者将在一栋两层楼的建筑中进行比赛。每层楼将排列一排 $n$ 张桌子。每层楼的桌子从左到右编号，从 1 开始。有一部楼梯允许参赛者在两层之间通行。建筑的结构如下图所示：\n\n对于每张桌子，已知是否会有队伍在此桌工作。\n\n组织者决定安装一台打印机，以便参赛者打印他们的解决方案。为此，他们必须选择一层楼放置打印机，并在该层选择一张桌子。打印机可以安装在任意一张桌子上（可以是空桌，也可以是某个队伍将使用的桌子）。\n\n我们定义每个队伍的不便值。例如，队伍 $i$ 将坐在楼层 $f_i$ 的桌子 $a_i$ 上，而打印机安装在楼层 $f_p$ 的桌子 $a_p$ 上。如果打印机安装在队伍 $i$ 所在的同一层（即 $f_i = f_p$），则队伍 $i$ 的不便值为 $| a_i - a_p |$。如果打印机安装在另一层（即 $f_i \\ne f_p$），则队伍 $i$ 的不便值为 $a_i + k + a_p$：队伍需先走到其所在房间的出口（对应 $a_i$），然后通过楼梯到达另一层（对应 $k$），再走到打印机所在的桌子（对应 $a_p$）。\n\n组织者希望放置打印机，使得所有队伍中的最大不便值最小化。你的任务是帮助他们：告知他们打印机应放置在哪一层、哪一张桌子。\n\n第一行包含两个整数 $n$ 和 $k$ $(1 \\le n \\le 1\\,000, 1 \\le k \\le 1\\,000)$ —— 每层楼的桌子数量，以及通过楼梯到达另一层所需的时间。\n\n第二行包含一个长度为 $n$ 的字符串，每个字符为 0 或 1。该字符串对应第二层桌子上的队伍分布：如果第 $i$ 个字符是 1，则第二层第 $i$ 张桌子将有队伍；否则该桌子为空。\n\n第三行包含一个长度为 $n$ 的字符串，每个字符为 0 或 1。该字符串对应第一层桌子上的队伍分布：如果第 $i$ 个字符是 1，则第一层第 $i$ 张桌子将有队伍；否则该桌子为空。\n\n保证至少有一个队伍参加训练营（即这两个字符串中至少有一个字符是 1）。\n\n第一行应输出一个整数 —— 所有队伍中可能的最小最大不便值。\n\n第二行应输出两个整数 —— 打印机应放置的楼层编号和桌子编号。如果有多个最优解，输出任意一个即可。\n\n在第一个示例中，可以将打印机放置在第一层第 1 张桌子。此时，第二层队伍的不便值为 $3 + 2 + 1 = 6$，第一层队伍的不便值为 $| 1 - 3 | = 2$。因此最小可能的最大不便值为 $6$。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $k$ $(1 \\le n \\le 1\\,000, 1 \\le k \\le 1\\,000)$ —— 每层楼的桌子数量，以及通过楼梯到达另一层所需的时间。第二行包含一个长度为 $n$ 的字符串，每个字符为 0 或 1。该字符串对应第二层桌子上的队伍分布：如果第 $i$ 个字符是 1，则第二层第 $i$ 张桌子将有队伍；否则该桌子为空。第三行包含一个长度为 $n$ 的字符串，每个字符为 0 或 1。该字符串对应第一层桌子上的队伍分布：如果第 $i$ 个字符是 1，则第一层第 $i$ 张桌子将有队伍；否则该桌子为空。保证至少有一个队伍参加训练营（即这两个字符串中至少有一个字符是 1）。"},{"iden":"output","content":"第一行应输出一个整数 —— 所有队伍中可能的最小最大不便值。第二行应输出两个整数 —— 打印机应放置的楼层编号和桌子编号。如果有多个最优解，输出任意一个即可。"},{"iden":"examples","content":"输入\n3 2\n001\n001\n输出\n6\n1 1\n\n输入\n10 2\n0001011011\n1000000000\n输出\n7\n2 3"},{"iden":"note","content":"在第一个示例中，可以将打印机放置在第一层第 1 张桌子。此时，第二层队伍的不便值为 $3 + 2 + 1 = 6$，第一层队伍的不便值为 $| 1 - 3 | = 2$。因此最小可能的最大不便值为 $6$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ be the number of tables per floor and the staircase cost, respectively.  \nLet $ S_2 \\in \\{0,1\\}^n $ be the binary string representing occupied tables on the **second** floor: $ S_2[i] = 1 $ iff a team sits at table $ i+1 $ on floor 2.  \nLet $ S_1 \\in \\{0,1\\}^n $ be the binary string representing occupied tables on the **first** floor: $ S_1[i] = 1 $ iff a team sits at table $ i+1 $ on floor 1.  \n\nLet $ T_1 = \\{ i \\in \\{1, \\dots, n\\} \\mid S_1[i-1] = 1 \\} $ be the set of table indices on floor 1 with teams.  \nLet $ T_2 = \\{ i \\in \\{1, \\dots, n\\} \\mid S_2[i-1] = 1 \\} $ be the set of table indices on floor 2 with teams.  \nLet $ T = T_1 \\cup T_2 $ be the set of all teams.\n\nLet $ p \\in \\{1,2\\} \\times \\{1, \\dots, n\\} $ be the printer placement: $ p = (f_p, a_p) $, where $ f_p \\in \\{1,2\\} $ is the floor, $ a_p \\in \\{1, \\dots, n\\} $ is the table.\n\n**Inconvenience Function**  \nFor a team at $ (f_i, a_i) \\in T $, the inconvenience to printer at $ (f_p, a_p) $ is:  \n$$\nd((f_i, a_i), (f_p, a_p)) = \n\\begin{cases}\n|a_i - a_p| & \\text{if } f_i = f_p \\\\\na_i + k + a_p & \\text{if } f_i \\ne f_p\n\\end{cases}\n$$\n\n**Objective**  \nFind $ p^* = (f_p^*, a_p^*) \\in \\{1,2\\} \\times \\{1, \\dots, n\\} $ minimizing:  \n$$\n\\max_{(f_i, a_i) \\in T} d((f_i, a_i), (f_p^*, a_p^*))\n$$\n\nOutput the minimal maximum inconvenience and any optimal $ p^* $.","simple_statement":null,"has_page_source":false}