codeforces-scrape

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

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