PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
1119
PREREQUISITES:
None
PROBLEM:
Chef wants to kill N weeds using herbicide within M days.
The i-th weed shows up on day A_i.
Each weed requires K applications of herbicide, and on each day there can be at most one application.
However, all present weeds will be affected by the application.
Can Chef kill all the weeds within M days?
EXPLANATION:
First off, Chef certainly needs to be able to kill the last weed, that pops up on day A_N.
It requires K days to do so, so the first day on which Chef can do so is day A_N+K-1 (because the first day is A_N itself).
So, surely if M \lt A_N+K-1, the answer is No.
On the other hand, if M\geq A_N+K-1, the answer is always Yes.
This is because the herbicide affects all active weeds — so, Chef can simply wait till day A_N before he starts applying the herbicide; and all the weeds will die at the same time as the N-th one.
TIME COMPLEXITY
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
print('Yes' if a[-1] + k - 1 <= m else 'No')