A field operative must complete n missions, in order. Mission i has a stamina requirement fatigue_i and a reputation requirement clout_i. To take on mission i, the operative's current stamina must be strictly greater than fatigue_i, and current reputation must be strictly greater than clout_i; both conditions must hold at once. Immediately after completing mission i, stamina decreases by fatigue_i (the toll of the job) and reputation increases by clout_i (the fame earned). Before the sequence begins, the operative starts with stamina S and reputation R, and may spend any number of preparation hours; each hour raises either starting stamina by 1 or starting reputation by 1 (never both in the same hour). Determine the minimum number of preparation hours needed so the operative can complete all n missions, in order, without ever violating either requirement.
n, S, R.A single integer: the minimum number of preparation hours required.
Example 1
Input
2 1 1 1 1 1 1
Expected
3
Explanation
Stamina needs total fatigue 2, so it must start at 3, costing 2 hours (starts at 1). For reputation: starting at 1, mission 1 needs >1 so 1 hour raises it to 2, giving 1 hour spent and reputation becomes 2+1=3 after the mission; mission 2 needs >1 and 3 already qualifies, ending at 3+1=4. Reputation costs 1 hour, so the total is 2+1=3.
Example 2
Input
3 5 1 3 2 1 1 4 2
Expected
5
Explanation
Total fatigue is 6, so stamina must start at 7, costing 2 hours (starts at 5). For reputation starting at 1: mission 1 needs >1, so 1 hour brings it to 2, then +1 clout makes it 3 (1 hour spent so far); mission 2 needs >4, current 3 is not enough so 2 hours bring it to 5, then +4 clout makes it 9 (3 hours spent so far); mission 3 needs >2 and 9 already qualifies, ending at 9+2=11. Reputation costs 3 hours, so the total is 2+3=5.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →