ORANGES - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef ate N oranges, each with 10, 11, or 12 slices. Is it possible that he ate exactly K slices?

EXPLANATION:

The minimum number of slices Chef could have possibly eaten is 10\cdot N, since each orange has at least 10 slices.
Similarly, the maximum number of slices is 12\cdot N.

So, if K \lt 10\cdot N or K\gt 12\cdot N, we can immediately say that it’s impossible for Chef to have eaten exactly K slices.

That leaves the case when 10\cdot N \leq K \leq 12\cdot N.
In such a case, there always exists a way for Chef to have eaten exactly K slices, so the answer is Yes.

Why?

Start with N oranges, each with 10 slices.
Let S denote the total number of slices. Initially, S = 10\cdot N.

Then, while S \lt K, do the following:

  • Choose some orange with less than 12 slices, and increase its number of slices by 1.

Since we increase the number of slices by 1 each time, S cannot ‘skip’ over values, and so will eventually equal K - after all, as long as S \lt 12\cdot N there will always exist an orange with less than 12 slices available for us to choose, so the process can only stop when all oranges have 12 slices.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    mn, mx = 10*n, 12*n
    print('Yes' if mn <= k <= mx else 'No')