Woburn Challenge 2018-19 Round 4 - Junior Division
Today, Billy feels the need to unwind by returning to one of his favourite video games, the classic role-playing game Paper Mario. There's nothing more satisfying than replaying the final boss battle against Bowser!
When in battle, Mario's current health is represented by an integral "HP" value. His HP begins at , and may increase or decrease over the course of the battle.
While battling against Bowser, a sequence of events will occur, the -th of which will cause Mario's HP to increase by . Note that may either be negative (indicating an attack by Bowser) or positive (indicating a healing item used by Mario). If an event would cause Mario's HP to become greater than , it instead becomes equal to exactly . On the other hand, if an event would cause Mario's HP to become less than or equal to , then let's just say that our hero's in trouble!
However, Billy has planned against such an eventuality, by stocking Mario up on an abundance of Life Shroom items. When Mario's HP becomes less than or equal to , he automatically consumes a Life Shroom, which restores his HP and causes it to become equal to instead!
Assuming that Mario will never run out of Life Shrooms, help Billy determine how many of them Mario will consume over the course of the entire battle.
Input Specification
The first line of input consists of a single integer, .
lines follow, the -th of which consists of a single integer,
, for .
Output Specification
Output a single integer, the number of Life Shrooms which Mario will consume.
Sample Input
6
-30
-20
50
-59
1
-10
Sample Output
2
Sample Explanation
- After the -st event, Mario's HP will drop to .
- After the -nd event, Mario's HP will drop to , causing him to consume a Life Shroom and have his HP restored to .
- After the -rd event, Mario's HP will increase to the limit of .
- After the -th event, Mario's HP will drop below , resulting in the consumption of another Life Shroom.
- After the -th event, Mario's HP will increase to .
- After the -th event, Mario's HP will drop to .
Overall, Mario will have consumed Life Shrooms (after the -nd and -th events).
Comments