← 返回题目列表

Codeforces · 1165/A

A. 余数

中文机器翻译题面 查看原题

给你一个巨大的十进制数字,由 $$$n$$$ 数字组成。确保该数字没有前导零。该数字的每个数字要么是 0,要么是 1。

您可以使用此数字执行多次(可能为零)操作。在每次操作期间,您可以更改号码的任意数字;您可以将0更改为1或1更改为0。经过某些操作,您可能会得到一个带有前导零的数字,但这对这个问题来说并不重要。

还给你两个整数 $$$0 \le y < x < n$$$。您的任务是计算为获得对 $$$10^x$$$ 取余数 $$$10^y$$$ 的数应执行的最少运算次数。换句话说,得到的数字除以$$$10^x$$$后应有余数$$$10^y$$$。

输入

输入的第一行包含三个整数 $$$n, x, y$$$ ($$$0 \le y < x < n \le 2 \cdot 10^5$$$) — 分别是数字和整数 $$$x$$$ 和 $$$y$$$ 的长度。

输入的第二行包含一个由$$$n$$$位组成的十进制数,该数字的每一位不是0就是1。保证该数字的第一位是1。

输出

打印一个整数 — 为获得对 $$$10^x$$$ 取余数 $$$10^y$$$ 的数,应执行的最少运算次数。换句话说,得到的数字除以$$$10^x$$$后应有余数$$$10^y$$$。

示例

输入 #1

11 5 2
11010100101

输出 #1

1

输入 #2

11 5 1
11010100101

输出 #2

3

注意

在第一个示例中,执行一次操作后,数字将为 $$$11010100100$$$。它的余数是 $$$100$$$ 对 $$$100000$$$ 取模。

在第二个示例中,执行三个操作后,数字将为 $$$11010100010$$$。它的余数为 $$$10$$$ 对 $$$100000$$$ 取模。