codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1165A.md (1923B)


      1 Source: https://codeforces.com/problemset/problem/1165/A
      2 
      3 A. Remainder
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a huge decimal number consisting of $n$ digits. It is guaranteed that this number has no leading zeros. Each digit of this number is either 0 or 1.
     22 
     23 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.
     24 
     25 You are also given two integers $0 \le y \lt x \lt n$. Your task is to calculate the minimum number of operations you should perform to obtain the number that has remainder $10^y$ modulo $10^x$. In other words, the obtained number should have remainder $10^y$ when divided by $10^x$.
     26 
     27 Input
     28 
     29 The first line of the input contains three integers $n, x, y$ ($0 \le y \lt x \lt n \le 2 \cdot 10^5$) — the length of the number and the integers $x$ and $y$, respectively.
     30 
     31 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.
     32 
     33 Output
     34 
     35 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$.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 11 5 2
     43 11010100101
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 1
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 11 5 1
     56 11010100101
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 3
     63 ```
     64 
     65 Note
     66 
     67 In the first example the number will be $11010100100$ after performing one operation. It has remainder $100$ modulo $100000$.
     68 
     69 In the second example the number will be $11010100010$ after performing three operations. It has remainder $10$ modulo $100000$.