2176B.md (2153B)
1 Source: https://codeforces.com/problemset/problem/2176/B 2 3 B. Optimal Shifts 4 5 time limit per test 6 7 1.5 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 $s_1s_2 \ldots s_n$, containing at least one 1. You want to obtain a binary string of the same length, consisting only of 1s. To do this, you can perform the following operation any number of times: 22 23 Choose a number $d$ ($1 \le d \le n$) and consider the string $t$ as a cyclic right shift of the string $s$ by $d$, or, more formally, $t = s_{n - d + 1} \ldots s_{n}s_{1} \ldots s_{n - d}$. After that, for all $j$ for which $t_j = 1$, perform $s_j := 1$. The described operation costs $d$ coins, where $d$ is the chosen shift amount. 24 25 Note that the positions $j$ in the string $s$, where initially $s_j=1$, remain equal to $1$ even if $t_j=0$. 26 27 You need to determine the minimum number of coins that can be spent so that the string $s$ consists only of 1s after all operations. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 32 33 The first line of each test case contains the number $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the given binary string. 34 35 The second line of each test case contains a binary string of length $n$, each element of which is either 0 or 1. 36 37 It is guaranteed that at least one character in each string is equal to 1. 38 39 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output the answer to it — the minimum possible number of coins that you can spend to make all characters in the string equal to 1. 44 45 Example 46 47 Input 48 49 ``` 50 5 51 52 1 53 54 1 55 56 3 57 58 101 59 60 4 61 62 0110 63 64 11 65 66 10101010100 67 68 2 69 70 11 71 ``` 72 73 Output 74 75 ``` 76 0 77 78 1 79 80 2 81 82 2 83 84 0 85 ``` 86 87 Note 88 89 Consider the third example, where $s = $ "0110". In this case, it is optimal to choose $d = 2$, then $t = $ "1001". After that, at positions $j = 1$ and $j = 4$, $s_j$ will be replaced with 1, resulting in the string $s$ consisting of all ones. Note that the cost of this operation is $d = 2$.