codeforces-scrape

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

1971D.md (1774B)


      1 Source: https://codeforces.com/problemset/problem/1971/D
      2 
      3 D. Binary Cut
      4 
      5 time limit per test
      6 
      7 2 seconds
      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$^{\dagger}$. Please find the minimum number of pieces you need to cut it into, so that the resulting pieces can be rearranged into a sorted binary string.
     22 
     23  ![](https://espresso.codeforces.com/d5649738d6458ef48c0f2a5c9984ece694ec3277.png) 
     24 
     25 Note that:
     26 
     27 * each character must lie in exactly one of the pieces;
     28 * the pieces must be contiguous substrings of the original string;
     29 * you must use all the pieces in the rearrangement.
     30 
     31 $^{\dagger}$ A binary string is a string consisting of characters $\texttt{0}$ and $\texttt{1}$. A sorted binary string is a binary string such that all characters $\texttt{0}$ come before all characters $\texttt{1}$.
     32 
     33 Input
     34 
     35 The first line contains a single integer $t$ ($1 \leq t \leq 500$) — the number of test cases.
     36 
     37 The only line of each test case contains a single string $s$ ($1 \leq |s| \leq 500$) consisting of characters $\texttt{0}$ and $\texttt{1}$, where $|s|$ denotes the length of the string $s$.
     38 
     39 Output
     40 
     41 For each test case, output a single integer — the minimum number of pieces needed to be able to rearrange the string into a sorted binary string.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 6
     49 
     50 11010
     51 
     52 00000000
     53 
     54 1
     55 
     56 10
     57 
     58 0001111
     59 
     60 0110
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 3
     67 1
     68 1
     69 2
     70 1
     71 2
     72 ```
     73 
     74 Note
     75 
     76 The first test case is pictured in the statement. It can be proven that you can't use fewer than $3$ pieces.
     77 
     78 In the second and third test cases, the binary string is already sorted, so only $1$ piece is needed.
     79 
     80 In the fourth test case, you need to make a single cut between the two characters and rearrange them to make the string $\texttt{01}$.