PROBLEM LINK:
Author: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Suchan Park
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There are N hills in a row. The height of the i-th hill is H[i]. Chef is initially on the 1st hill.
When Chef is at hill i, Chef can jump to the adjacent hill j if and only if H[i] - D \le H[j] \le H[j] + U without a parachute, and H[j] < H[i] with a parachute. Chef is allowed to use the parachute at most once.
Find the rightmost hill that the Chef can reach.
QUICK EXPLANATION:
Simulate the whole process. Use the parachute as late as possible.
EXPLANATION:
Since the Chef can only jump to the adjacent hill, we can make a for-loop that iterates the current position of Chef.
Using the parachute when the Chef can jump without the parachute is obviously a waste. Therefore the Chef should continuously jump without a parachute as long as he can.
So, we can simulate the whole process using a for loop, like this:
for i = 1 to N: // i denotes the position of the Chef
if (i == N) {
// If the Chef is on the rightmost hill,
// there is nothing to do.
}
else if (H[i] - D <= H[i+1] <= H[i] + U) {
// if the Chef is able to jump on his own,
// just jump without a parachute
}
else if (H[i+1] < H[i]) {
// Chef can jump if the parachute is left
if(parachute isn't used) {
Use the parachute.
}else {
Break the loop. (since the Chef cannot jump)
}
}
else {
// Chef cannot jump when the next hill is too high
Break the loop. (since the Chef cannot jump)
}
One can check whether the parachute is used or not by setting a boolean-type variable. (true if used, false otherwise)
The answer will be the maximum i visited during the loop.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.