Seats

We need the minimum total number of occupied seats in a final valid state.

A final state is valid and “full” exactly when it is a maximal independent set on the path:

• no two occupied seats are adjacent;
• every empty seat has an occupied neighbor, otherwise we could still place someone there.

The existing 1s are fixed. So the job is not “place as many as possible”; it is the opposite: place as few extra students as possible while making every remaining 0 unplaceable.

Consider one maximal block of zeros. Suppose its length is $L$.

There may be an existing 1 immediately to the left of the block, and/or immediately to the right. Each such neighboring 1 already handles one boundary zero:

• that boundary zero cannot be occupied because it is adjacent to a 1;
• it is already dominated, so we do not need to cover it with a new student.

So if the block has $b$ occupied neighbors around it, where $b \in \{0,1,2\}$, the part still needing new students has length

$$m = \max(0, L - b).$$

Now we need the minimum number of students to make a clean path segment of length $m$ maximal, with no outside help.

One newly occupied seat can cover at most three seats: itself, its left neighbor, and its right neighbor. Therefore at least

$$\left\lceil \frac{m}{3} \right\rceil$$

students are necessary.

This bound is also achievable: place students every three seats, for example at positions $2,5,8,\ldots$ inside the segment, adjusting at the end if needed. Each chosen seat covers a block of up to three consecutive seats, and chosen seats are never adjacent. So the exact answer for that zero block is

$$\left\lceil \frac{m}{3} \right\rceil.$$

In integer arithmetic:

$$\left\lceil \frac{m}{3} \right\rceil = \frac{m+2}{3}.$$

Then the final answer is:

1. count all existing 1s;
2. split the string into maximal zero blocks;
3. for each block, subtract the number of adjacent existing 1s from its length;
4. add $\frac{m+2}{3}$ for the remaining length $m$.

This also handles the annoying edge cases cleanly:

• all zeros: one zero block with $b=0$, answer $\left\lceil n/3 \right\rceil$;
• one seat: 0 gives $1$, 1 gives $1$;
• blocks like 1001: the middle block has $L=2$, $b=2$, so $m=0$ and no extra student is needed;
• already maximal rows naturally add zero extra students.

The algorithm is a single scan over the string.

Complexity:

$$O(n)$$

per test case, and

$$O(1)$$

extra memory besides the input string. No drama, no DP hammer for a nail-sized problem.