A. Remainder Codeforces Round #560 (Div. 3)

You are given a huge decimal number consisting of nn digits. It is

guaranteed that this number has no leading zeros. Each digit of this

number is either 0 or 1.

You may perform several (possibly zero) operations with this number.

During each operation you are allowed to change any digit of your

number; you may change 0 to 1 or 1 to 0. It is possible that after

some operation you can obtain a number with leading zeroes, but it

does not matter for this problem.

You are also given two integers 0≤y<x<n0≤y<x<n. Your task is to

calculate the minimum number of operations you should perform to

obtain the number that has remainder 10y10y modulo 10x10x. In other

words, the obtained number should have remainder 10y when divided by

10x.

Input

The first line of the input contains three integers n,x,y

(0≤y<x<n≤2⋅1050≤y<x<n≤2⋅105) — the length of the number and the

integers x and y, respectively.

The second line of the input contains one decimal number consisting of

n digits, each digit of this number is either 0 or 1. It is guaranteed

that the first digit of the number is 1.

Output

Print one integer — the minimum number of operations you should

perform to obtain the number having remainder 10的y次幂 modulo 10的x次幂. In

other words, the obtained number should have remainder 10的y次幂 when

divided by 10的x次幂.

Examples

input

Copy

11 5 2

11010100101

output

Copy

1

input

Copy

11 5 1

11010100101

output

Copy

3

Note

In the first example the number will be 1101010010011010100100 after

performing one operation. It has remainder 100100 modulo 100000100000.

In the second example the number will be 1101010001011010100010 after

performing three operations. It has remainder 1010 modulo

100000100000.

题解如下

#include<iostream>

#include<string.h>

using namespace std;

const int Len = 5e5;

char ar[Len];

int main()

{

    //freopen("test.txt","r",stdin);

    int n,x,y;

    scanf("%d %d %d",&n,&x,&y);

    scanf("%s",ar + 1);

    int ans = 0;

    for(int i = n - x + 1; i <= n; i ++)	//在[n-x+1,n] 这个区间内的数字进行一一讨论，如果与当前位 的数字不是自己想要的 ans ++

    {

        if(i < n - y)

        {

            if(ar[i] != '0')

                ans ++;

        }

        else if(i == n - y)

        {

            if(ar[i] != '1')

                ans ++;

        }

        else

        {

            if(ar[i] != '0')

                ans ++;

        }

    }

    printf("%d",ans);

    return 0;

}

巴特西

A. Remainder Codeforces Round #560 (Div. 3)

A. Remainder Codeforces Round #560 (Div. 3)

题解如下

最新文章

热门文章