codeforces-scrape

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

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