MINNOO - Editorial

Author: Shah Achyut
Testers: Nishank Suresh, Tejas Pandey
Editorialist: Nishank Suresh

604

None

PROBLEM:

What is the minimum number of ones a binary string B of length N must contain so that \max(b_i, b_{i+1}) = 1 for every 1 \leq i \lt N?

EXPLANATION:

\max(b_i, b_{i+1}) = 1 means that between any two adjacent characters, at least one of them must be 1.

To minimize the number of ones, it’s thus best to have an alternating string of length N starting with 0, i.e, 01010101\ldots

The number of 1's in such a string is exactly

\left\lfloor \frac{N}{2} \right\rfloor

for _ in range(int(input())):