codeforces-scrape

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

1680C.md (1859B)


      1 Source: https://codeforces.com/problemset/problem/1680/C
      2 
      3 C. Binary String
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a string $s$ consisting of characters 0 and/or 1.
     22 
     23 You have to remove several (possibly zero) characters from the beginning of the string, and then several (possibly zero) characters from the end of the string. The string may become empty after the removals. The cost of the removal is the maximum of the following two values:
     24 
     25 * the number of characters 0 left in the string;
     26 * the number of characters 1 removed from the string.
     27 
     28 What is the minimum cost of removal you can achieve?
     29 
     30 Input
     31 
     32 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     33 
     34 Each test case consists of one line containing the string $s$ ($1 \le |s| \le 2 \cdot 10^5$), consisting of characters 0 and/or 1.
     35 
     36 The total length of strings $s$ in all test cases does not exceed $2 \cdot 10^5$.
     37 
     38 Output
     39 
     40 For each test case, print one integer — the minimum cost of removal you can achieve.
     41 
     42 Example
     43 
     44 Input
     45 
     46 ```
     47 5
     48 
     49 101110110
     50 
     51 1001001001001
     52 
     53 0000111111
     54 
     55 00000
     56 
     57 1111
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 1
     64 3
     65 0
     66 0
     67 0
     68 ```
     69 
     70 Note
     71 
     72 Consider the test cases of the example:
     73 
     74 1. in the first test case, it's possible to remove two characters from the beginning and one character from the end. Only one 1 is deleted, only one 0 remains, so the cost is $1$;
     75 2. in the second test case, it's possible to remove three characters from the beginning and six characters from the end. Two characters 0 remain, three characters 1 are deleted, so the cost is $3$;
     76 3. in the third test case, it's optimal to remove four characters from the beginning;
     77 4. in the fourth test case, it's optimal to remove the whole string;
     78 5. in the fifth test case, it's optimal to leave the string as it is.