PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh_07
Tester: mridulahi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have X large ornaments, Y small ornaments, and a Christmas tree with N leaves.
Each leaf must be decorated with either 1 large and 3 small ornaments, or 2 large ornaments.
Can you decorate all N leaves?
EXPLANATION:
Let’s denote the two types of decorations by (1, 3) and (2, 0).
It’s optimal to decorate as many leaves as possible using type (1, 3) decorations; and then try to decorate the rest with (2, 0).
Why?
The intuition here is that type (2, 0) is more “free” because it doesn’t use any small ornaments at all, and so can be saved for later — also, (1, 3) uses less large ornaments.
So, if you have \geq 3 unused small ornaments, and have already decorated a leaf with type (2, 0), you can instead switch it to a type (1, 3) decoration: this way, you save one large ornament which might allow for more decorations in the future.
WIth this in mind, we’ll try to find the maximum number of leaves that can be decorated.
Let K = \min(X, \left\lfloor \frac{Y}{3} \right\rfloor). Here, \left\lfloor \ \ \right\rfloor denotes the floor function.
Note that K is the maximum number of type (1, 3) decorations we can form.
Each of them uses one large ornament, so we’re left with (X-K) large ornaments in the end.
So, we can decorate another \left\lfloor\frac{X-K}{2}\right\rfloor leaves using them.
Thus, the maximum number of leaves that can be decorated is
with K = \min(X, \left\lfloor \frac{Y}{3} \right\rfloor).
If this quantity is less than N, decorating all N leaves is impossible; otherwise we’ll be able to decorate them.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, x, y = map(int, input().split())
used = min(x, y//3)
best = used + (x-used)//2
print('Yes' if best >= n else 'No')