PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Shah Achyut
Testers: Nishank Suresh, Tejas Pandey
Editorialist: Nishank Suresh
DIFFICULTY:
604
PREREQUISITES:
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
which is hence our answer.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
print(int(input())//2)