PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You are at position X, and have two dice that will each roll an integer in [Y, Y+5].
You will move forward by the sum of the rolled values.
Is it possible for you to end up on exactly position 50?
EXPLANATION:
Both dice will roll a value in [Y, Y+5].
So, the minimum possible number of steps that you will move is when both dice roll Y, for 2Y steps.
Similarly, the maximum number of steps that can be moved is 2\cdot (Y+5) = 2Y+10.
This means that:
- If X + 2Y \gt 50, it’s not possible to end up at exactly 50: you will always end up after it.
- If X + 2Y + 10 \lt 50, it’s again not possible to end up at 50: you will never even reach it.
That leaves the case of X+2Y \le 50 \le X+2Y+10.
In this case, it’s always possible to reach 50, because the dice consist of consecutive integers.
For example: start with both dice rolling Y, so you end up at X + 2Y.
Now, repeatedly increase the value rolled on one of the dice (as long as you don’t exceed Y+5, of course).
This is guaranteed to reach 50 at some point, because you start before 50 and end after it - and moving one step at a time, nothing can be skipped.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
x, y = map(int, input().split())
print('Yes' if x+2*y <= 50 <= x+2*y+10 else 'No')