1969B.md (2064B)
1 Source: https://codeforces.com/problemset/problem/1969/B 2 3 B. Shifts and Sorting 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 Let's define a cyclic shift of some string $s$ as a transformation from $s_1 s_2 \dots s_{n-1} s_{n}$ into $s_{n} s_1 s_2 \dots s_{n-1}$. In other words, you take one last character $s_n$ and place it before the first character while moving all other characters to the right. 22 23 You are given a binary string $s$ (a string consisting of only 0-s and/or 1-s). 24 25 In one operation, you can choose any substring $s_l s_{l+1} \dots s_r$ ($1 \le l \lt r \le |s|$) and cyclically shift it. The cost of such operation is equal to $r - l + 1$ (or the length of the chosen substring). 26 27 You can perform the given operation any number of times. What is the minimum total cost to make $s$ sorted in non-descending order? 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 The first and only line of each test case contains a binary string $s$ ($2 \le |s| \le 2 \cdot 10^5$; $s_i \in$ {0, 1}) — the string you need to sort. 34 35 Additional constraint on the input: the sum of lengths of strings over all test cases doesn't exceed $2 \cdot 10^5$. 36 37 Output 38 39 For each test case, print the single integer — the minimum total cost to make string sorted using operation above any number of times. 40 41 Example 42 43 Input 44 45 ``` 46 5 47 48 10 49 50 0000 51 52 11000 53 54 101011 55 56 01101001 57 ``` 58 59 Output 60 61 ``` 62 2 63 0 64 9 65 5 66 11 67 ``` 68 69 Note 70 71 In the first test case, you can choose the whole string and perform a cyclic shift: 10 $\rightarrow$ 01. The length of the substring is $2$, so the cost is $2$. 72 73 In the second test case, the string is already sorted, so you don't need to perform any operations. 74 75 In the third test case, one of the optimal strategies is the next: 76 77 1. choose substring $[1, 3]$: 11000 $\rightarrow$ 01100; 78 2. choose substring $[2, 4]$: 01100 $\rightarrow$ 00110; 79 3. choose substring $[3, 5]$: 00110 $\rightarrow$ 00011. 80 81 The total cost is $3 + 3 + 3 = 9$.