1437B.md (1736B)
1 Source: https://codeforces.com/problemset/problem/1437/B 2 3 B. Reverse Binary Strings 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 string $s$ of even length $n$. String $s$ is binary, in other words, consists only of 0's and 1's. 22 23 String $s$ has exactly $\frac{n}{2}$ zeroes and $\frac{n}{2}$ ones ($n$ is even). 24 25 In one operation you can reverse any substring of $s$. A substring of a string is a contiguous subsequence of that string. 26 27 What is the minimum number of operations you need to make string $s$ alternating? A string is alternating if $s_i \neq s_{i + 1}$ for all $i$. There are two types of alternating strings in general: 01010101... or 10101010... 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. 32 33 The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$; $n$ is even) — the length of string $s$. 34 35 The second line of each test case contains a binary string $s$ of length $n$ ($s_i \in$ {0, 1}). String $s$ has exactly $\frac{n}{2}$ zeroes and $\frac{n}{2}$ ones. 36 37 It's guaranteed that the total sum of $n$ over test cases doesn't exceed $10^5$. 38 39 Output 40 41 For each test case, print the minimum number of operations to make $s$ alternating. 42 43 Example 44 45 Input 46 47 ``` 48 3 49 2 50 10 51 4 52 0110 53 8 54 11101000 55 ``` 56 57 Output 58 59 ``` 60 0 61 1 62 2 63 ``` 64 65 Note 66 67 In the first test case, string 10 is already alternating. 68 69 In the second test case, we can, for example, reverse the last two elements of $s$ and get: 0110 $\rightarrow$ 0101. 70 71 In the third test case, we can, for example, make the following two operations: 72 73 1. 11101000 $\rightarrow$ 10101100; 74 2. 10101100 $\rightarrow$ 10101010.