PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Chef has X rupees.
Can he give 7 gifts to Chefina, all with positive value, such that the value of the each gift is at least twice the value of the previous one?
EXPLANATION:
Let’s try to keep Chef’s costs down.
On the first day, the lowest we can do is give the gift a value of 1.
The second day should be at least twice this, meaning the best we can do is 2.
The third day should be at least twice this, meaning the best we can do is 4.
More generally, on the i-th day, the best Chef can do is to buy a gift with value 2^{i-1}.
So, for all seven days, the minimum total cost is 1+2+4+8+16+32+64 = 127.
Hence, if X \lt 127 it’s impossible for Chef to have enough money to buy all the gifts.
On the other hand, if X \geq 127, it’s always possible: make the first 6 days have values 1, 2, 4, 8, 16, 32, and then the last day can have all the remaining value (which is at least 64, so the doubling condition is satisfied).
Thus, the answer is Yes if X \geq 127 and No otherwise.
TIME COMPLEXITY:
\mathcal{O}(\log\min(X, Y)) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
x = int(input())
print('Yes' if x >= 127 else 'No')