DecenTile Games have launched a new First Person Shooter soldier game, called the Call of War, that young gamers can play on their website. Our protagonist, Ninja (played by you) is a soldier whose mission is to kill all the enemies plotting against you. Your enemies are standing in a circle, numbered clockwise from 1 to n. Initially, the i-th enemy has ai health. You have only one pistol, and infinite bullet magazines. You have to shoot the enemies in order to kill them. Each bullet fired at the enemy decreases their health by 1 (deals 1 damage to it). When the health of some enemy i becomes 0 or less than 0, he dies and his grenade drops down and explodes, dealing bi damage to the next enemy (enemy i+1, if i<n, or enemy 1, if i=n). If the next enemy is already dead, then nothing happens. If the frag from the grenade kills the next enemy, even he drops a grenade, damaging the enemy after him and possibly triggering another explosion, and so on. You have to calculate the minimum number of bullets you need in order to kill all the enemies and win the game.
constraints 1 <= T <= 100 1 <= N <= 10^4 1 <= a, b <= 10^12
sampleinput 1 3 7 15 2 14 5 3 sample output 6 sample input 2 3 11 5 18 18 12 8 5 7 13 5 15 17 8 2 7 18 17 sample output 21 15
You need to maximize the damage done by grenades to minimize the number of bullets you fire. A simple observation is that you should kill enemies in increasing order, so that when the ith enemy dies, the enemy after it is alive and takes as much damage as possible min(a[i+1], b[i]). Not killing in order means that some enemies would not damage the next as the next is already dead.
So you only have to take the best result from all starting locations. You can solve this with n^2 brute-force since n is only up to 1e4.
time limit exceeded for brute force
Brute-force should pass if your time-limit is 2000ms, your implementation is efficient, and you are using C++. However, this problem is solvable in O(n). You need to calculate the new a values after detonation, and then get the total_extra_bullets you need. Then, for each starting index i, you can simply take total_extra_bullets + original a[i] — new a[i]. See my code below (in python):
t = int(input())
for _ in range(t):
␣␣␣␣n = int(input())
␣␣␣␣a = []
␣␣␣␣b = []
␣␣␣␣for __ in range(n):
␣␣␣␣␣␣␣␣aa, bb = [int(x) for x in input().split()]
␣␣␣␣␣␣␣␣a.append(aa); b.append(bb)
␣␣␣␣post_detonation = [-1] * n # store the remaining hp when you detonate all the grenades
␣␣␣␣for i in range(n):
␣␣␣␣␣␣␣␣post_detonation[(i + 1) % n] = max(0, a[(i + 1) % n] — b[i])
␣␣␣␣total_additional = sum(post_detonation)
␣␣␣␣ans = int(2e18) # use long long in C++
␣␣␣␣for i in range(n):
␣␣␣␣␣␣␣␣# Start by killing a[i]. Subtract the need to kill a[i] after detonations.
␣␣␣␣␣␣␣␣required = a[i] + total_additional — post_detonation[i]
␣␣␣␣␣␣␣␣ans = min(ans, required)
␣␣␣␣print(ans)