Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Arnold Drita.
Jetpack Hurdle Jumping
Problem Description:
It's year 2036 and the Olympic Games have just begun.
Andi’s great nephew, Andi Jr. is competing in the hurdle
jumping discipline. For those who don't know, hurdle jumping
is the race where one has to run and jump over the obstacles.
Well, in the future it’s a little different. They have
jetpacks now and they don't have to jump. They can just
speak: "Ok Google, start my jetpack." And the jetpack
will make them fly for a while, without wasting their
energies. How cool is that?!
Because of the global warming problems, our planet is
low on both diesel and food. Each person is allowed to
get up to a specific amount of food and diesel per month.
The games last for a month, so Andi Jr. has to manage
how he uses his resources. He asks your help to find
out how to use his jetpack efficiently so that he
spends the smallest amount of energy.
You will firstly be given the amount of energy (C)
he has in his body (calculated based of the calories
he has eaten up to the moment of the race). Then
you will be given the number of times he can use
his jetpack (J). Finally you will be given the
number of obstacles N and next N integers representing
the amount of calories this obstacle requires to be
jumped. Knowing that each time you use the jetpack,
you can jump over 2 obstacles, and you can’t use it
for the 2 next immediate obstacles as it needs time
to recharge, you are required to find the maximal
amount of calories he can have left in his body
after the race, or if there is no way for him to
finish his race based on his current fuel and energy
situation, output the number of calories he would
need more. See samples for clarifications.
Input specification
0 ≤ C ≤ 100000 and 0 ≤ J ≤ 100 and 0 ≤
N ≤ 1000.
Output specification
If he can finish the race with the given energy and fuel
constraints, output "Yes, he can save (Z) calories."
Where Z is the number of calories left. If he cannot
finish the race, output "No, he needs (S) more calories."
Where S is the minimal number of calories necessary to
finish the race. See the samples.
Sample Input I
100 1 10
2 17 3 20 9 15 20 20 8 20
|
Sample Input II
100 2 14
2 17 3 20 9 15 20 20 8 20 10 10 9 9
|
Sample Output I
Yes, he can save 6 calories.
|
Sample Output II
No, he needs 7 more calories.
|
Explanation Sample 1:
He can only jump once, so the best way would be
to jump over the 7th and 8th obstacle (both 20).
This totals for 94 calories. Since he has 100
calories left in his body, not only he can finish
the race, but also have 6 calories left.
Explanation Sample 2:
In this case, the most efficient way to use his
energies would be to jump over the 6th and 7th
obstacle (15, 20), be forced to wait for two
obstacles and immediately jump over the 10th and
11th obstacle (20,10). Using this method, he needs
107 calories, but he only has 100 so he cannot
finish the race.
Clarification:
He ca use the jetpack since the beginning (from
the first obstacle) but his jetpack is required
to be fully charged when crossing the finish line.
So he cannot just jump over the last two obstacles
and finish the race.
Äëÿ îòïðàâêè ðåøåíèé íåîáõîäèìî âûïîëíèòü âõîä.
|