2188B.md (2353B)
1 Source: https://codeforces.com/problemset/problem/2188/B 2 3 B. Seats 4 5 time limit per test 6 7 1 second 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 Cordell manages a row of $n$ seats at the Scuola Comunale di Musica Piova where students are strictly forbidden from sitting next to each other. 22 23 You are given a binary string$^{\text{∗}}$ $s$, where $s_i = \mathtt{1}$ indicates that the $i$-th seat has been occupied by a student, and $s_i = \mathtt{0}$ indicates that it is free now. It is guaranteed that no two adjacent seats are occupied currently. Cordell needs to add more students until it is impossible to seat anyone else in the row. However, she wants to achieve this state with as few students as possible. 24 25 Your task is to calculate the minimum total number of students seated when it is impossible to seat anyone else in the row. 26 27 $^{\text{∗}}$A binary string is a string where each character is either $\mathtt{0}$ or $\mathtt{1}$. 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 a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of seats in the row. 34 35 The second line of each test case contains the binary string $s$ of length $n$ ($s_i \in \{\mathtt{0}, \mathtt{1}\}$). It is guaranteed that no two adjacent characters are both $\mathtt{1}$. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case, output a single integer — the minimum total number of seated students. 42 43 Example 44 45 Input 46 47 ``` 48 5 49 50 1 51 52 0 53 54 3 55 56 000 57 58 5 59 60 00000 61 62 6 63 64 100101 65 66 13 67 68 0000100001000 69 ``` 70 71 Output 72 73 ``` 74 1 75 76 1 77 78 2 79 80 3 81 82 5 83 ``` 84 85 Note 86 87 In the first test case, $n = 1$ and the hall is initially empty. Because the row is still possible to seat any student, Cordell must place one student at seat $1$. Therefore, the minimum number of seated students is $1$. 88 89 In the third test case, Cordell can place two students at seats $1$ and $4$. It can be shown that she cannot place only one student so that the row is impossible to seat anyone more, so the answer is $2$. 90 91 In the fourth test case, no extra students can be seated, so Cordell can place no extra students, and the number of seated students is $3$.