codeforces-scrape

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

1691C.md (1873B)


      1 Source: https://codeforces.com/problemset/problem/1691/C
      2 
      3 C. Sum of Substrings
      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 binary string $s$ of length $n$.
     22 
     23 Let's define $d_i$ as the number whose decimal representation is $s_i s_{i+1}$ (possibly, with a leading zero). We define $f(s)$ to be the sum of all the valid $d_i$. In other words, $f(s) = \sum\limits_{i=1}^{n-1} d_i$.
     24 
     25 For example, for the string $s = 1011$:
     26 
     27 * $d_1 = 10$ (ten);
     28 * $d_2 = 01$ (one)
     29 * $d_3 = 11$ (eleven);
     30 * $f(s) = 10 + 01 + 11 = 22$.
     31 
     32 In one operation you can swap any two adjacent elements of the string. Find the minimum value of $f(s)$ that can be achieved if at most $k$ operations are allowed.
     33 
     34 Input
     35 
     36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows.
     37 
     38 First line of each test case contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $0 \le k \le 10^9$) — the length of the string and the maximum number of operations allowed.
     39 
     40 The second line of each test case contains the binary string $s$ of length $n$, consisting of only zeros and ones.
     41 
     42 It is also given that sum of $n$ over all the test cases doesn't exceed $10^5$.
     43 
     44 Output
     45 
     46 For each test case, print the minimum value of $f(s)$ you can obtain with at most $k$ operations.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 3
     54 
     55 4 0
     56 
     57 1010
     58 
     59 7 1
     60 
     61 0010100
     62 
     63 5 2
     64 
     65 00110
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 21
     72 22
     73 12
     74 ```
     75 
     76 Note
     77 
     78 * For the first example, you can't do any operation so the optimal string is $s$ itself. $f(s) = f(1010) = 10 + 01 + 10 = 21$.
     79 * For the second example, one of the optimal strings you can obtain is "0011000". The string has an $f$ value of $22$.
     80 * For the third example, one of the optimal strings you can obtain is "00011". The string has an $f$ value of $12$.