HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50679 - Jetpack Hurdle Jumping

Guest
• Review clarifications (1)

Section problems

• 50842 - Minimum Sum Triangle - DP
• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 51149 - One Piece Arena
• 50485 - Center of gravity of a plate
• 50674 - Collecting Eggs
• 50677 - The Cottage
• 50675 - Kruja Boys
• 50679 - Jetpack Hurdle Jumping
• 50673 - DNA Testing
• 50997 - Dynamic Knights
• 50936 - Saving the Soldiers
• 50979 - Minimum access cost for BST
• 51062 - Fish Pond II
• 51010 - Max Sequential Sum
• 51072 - Castle on chessboard
• 51075 - Shortest Path for Bishop

Feedback

If you notice incorrect translations in Contester, please let author know.

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.


Äëÿ îòïðàâêè ðåøåíèé íåîáõîäèìî âûïîëíèòü âõîä.

www.contester.ru