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  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}$.