PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: sezalmittal987
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Chef cuts a pizza first into halves, then quarters, then eighths, and so on; each time with a cut through the center.
When Chef has X pieces, how many of them are smaller than another piece?
EXPLANATION:
Each cut made by Chef takes two existing ‘large’ pieces and halves them, making them smaller. Note that this also increases the number of pieces by 2.
So, all the pieces will be of equal size only when there are 1, 2, 4, 8, 16, \ldots pieces present; namely, when X is a power of 2.
This is because, when all the pieces are equal, the next time they’ll become equal is when they’ve all been halved in size (and hence the number of pieces must have doubled).
So, if X is a power of 2, the answer is 0.
Beyond that, as we noted at the start, each cut takes two ‘large’ pieces and halves them both - thus creating four ‘small’ pieces.
Let k be the largest integer such that 2^k \leq X, that is, the largest power of 2 not exceeding X.
To reach X pieces, Chef must have made exactly \frac{(X - 2^k)}{2} cuts, since each cut creates two new pieces.
Each cut creates four small pieces, so the total number of small pieces is hence
Finding the integer k can be done in a brute force manner: just keep increasing it as long as 2^k \leq X.
TIME COMPLEXITY:
\mathcal{O}(\log X) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
x = int(input())
p = 1
while 2*p <= x: p *= 2
print(2*x - 2*p)