You and your friend are playing the game Mortal Kombat XI. You are trying to pass a…
- User
You and your friend are playing the game Mortal Kombat XI. You are trying to pass a challenge tower. There are n bosses in this tower, numbered from 1 to n. The type of the i-th boss is a_i. If the i-th boss is easy then its type is a_i = 0, otherwise this boss is hard and its type is a_i = 1.
During one session, either you or your friend can kill one or two bosses (neither you nor your friend can skip the session, so the minimum number of bosses killed during one session is at least one). After your friend session, your session begins, then again your friend session begins, your session begins, and so on. The first session is your friend's session.
Your friend needs to get good because he can't actually kill hard bosses. To kill them, he uses skip points. One skip point can be used to kill one hard boss.
Your task is to find the minimum number of skip points your friend needs to use so you and your friend kill all n bosses in the given order.
For example: suppose n = 8, a = [1, 0, 1, 1, 0, 1, 1, 1]. Then the best course of action is the following:
- your friend kills two first bosses, using one skip point for the first boss;
- you kill the third and the fourth bosses;
- your friend kills the fifth boss;
- you kill the sixth and the seventh bosses;
- your friend kills the last boss, using one skip point, so the tower is completed using two skip points.
You have to answer t independent test cases. Input
The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.
The first line of the test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of bosses. The second line of the test case contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 1), where a_i is the type of the i-th boss.
It is guaranteed that the sum of n does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5).
Output
For each test case, print the answer: the minimum number of skip points your friend needs to use so you and your friend kill all n bosses in the given order.
Example
Input
6 8 1 0 1 1 0 1 1 1 5 1 1 1 1 0 7 1 1 1 1 0 0 1 6 1 1 1 1 1 1 1 1 1 0
Output
2 2 2 2 1 0
Assistant
We are given a game: there are n bosses in order; each boss is either easy (0) or hard (1). Two players: friend (F) and you (Y). Sessions alternate starting with friend: F, Y, F, Y, ... In each session, the player can kill either 1 or 2 bosses (they must kill at least one, cannot kill zero). They cannot skip bosses; they must kill in order. They must kill all n bosses exactly once.
Friend cannot kill hard bosses without using a skip point; each skip point allows him to kill one hard boss (presumably during his session, if the boss is hard, he must use a skip point to kill it). You can kill any boss (hard or easy) without any cost. The goal is to minimize the number of skip points used by friend across all his sessions.
We need to compute minimal total skip points required.
Observation: Since friend only incurs cost on hard bosses that he personally kills, we want to assign the kills of hard bosses to you as much as possible. But we must respect the alternating sessions and the constraints that each session kills 1 or 2 bosses. So it's a kind of scheduling problem: we need to partition the sequence of n bosses into segments, each segment of length 1 or 2, alternating between friend and you. The first segment belongs to friend. The total cost is the number of hard bosses in friend's segments.
We want to choose a partition (i.e., decide after each kill how many bosses the current player kills, subject to constraints) that minimizes total cost.
This resembles DP. Since n up to 2e5 and sum n up to 2e5, we can do O(n) DP per test.
State: index i (0..n) representing we have processed first i bosses. Next turn? Whose turn? And possibly some constraint that the previous player might have killed 2? Actually we need to decide at each step. But it's simpler: we can think of DP[i][p] = minimal skip points used to kill first i bosses, and it's player p's turn to start next session (i.e., the next boss to kill is i+1, and the next session belongs to player p). However, we need to enforce that each session kills 1 or 2 bosses. So from state (i, p), we can transition to i+1 (if p kills one boss) or i+2 (if p kills two bosses). The cost incurred in transition: number of hard bosses among positions i+1 to i+k (k=1 or 2) multiplied by indicator that p is friend (since if p is you, cost 0). Then next turn becomes 1-p.
Thus DP: dp[i][p] = min cost to process first i bosses, with current turn = p (p=0 for friend, p=1 for you). dp[0][0] = 0 (since friend's turn first). dp[0][1] = infinity because game starts with friend.
Transition: For p in {0,1}:
- if i+1 <= n: cost = (p==0? sum a[i+1] : 0) + dp[i+1][1-p]
- if i+2 <= n: cost = (p==0? a[i+1]+a[i+2] : 0) + dp[i+2][1-p] Take min.
At the end, answer is min(dp[n][0], dp[n][1])? Actually after processing all n bosses, it doesn't matter whose turn it is; but we must have exactly used all bosses. So answer = min(dp[n][0], dp[n][1])? But we need to ensure that the last session ended after killing the last boss, and there is no requirement that the next player's turn must be anything. So both dp[n][0] and dp[n][1] are valid final states (if the last kill was by friend, then next turn is you, so we would have state (n, you); if last kill was by you, next turn is friend). So both are valid. So answer = min(dp[n][0], dp[n][1]).
We can compute dp forward (iterative) or backward. Since n up to 2e5 and sum n 2e5, DP with O(n) per test works.
But we need to be careful: dp array size (n+1)x2, okay.
Simplify: we can do DP with two arrays: dp_f[i] = min cost when it's friend's turn at position i (i processed), dp_y[i] similarly. Or do forward from 0.
Let's define dp[i][p] as minimal cost after processing i bosses, and now it's player p's turn to kill the next boss (i+1). Then base: dp[0][0] = 0, dp[0][1] = INF. Then for i from 0 to n-1: For p in {0,1} if dp[i][p] is finite: // kill 1 if i+1 <= n: new_cost = dp[i][p] + (p==0 ? a[i+1] : 0); if new_cost < dp[i+1][1-p] then update. // kill 2 if i+2 <= n: new_cost = dp[i][p] + (p==0 ? a[i+1]+a[i+2] : 0); if new_cost < dp[i+2][1-p] then update.
But careful: indices: a is 1-indexed. We'll have array a[1..n].
This is straightforward O(n). At the end answer = min(dp[n][0], dp[n][1]).
But is there any trick? The constraints: each session must kill exactly 1 or 2 bosses. This DP covers that.
But maybe we can further simplify: Since you have no cost, we want to assign as many hard bosses as possible to you. But there might be constraints: because friend must kill at least one per his session, and you also at least one per your session, alternating. However, the DP is simple enough.
But we can also think greedy? Let's examine: The pattern of kills: It's like an alternating sequence of moves of size 1 or 2. This is analogous to covering the line with segments of length 1 or 2, where segments alternate colors. The first segment is friend. The cost is number of 1's in friend segments.
Minimizing cost is like maximizing the number of hard bosses assigned to you. Equivalent to: choose a sequence of moves (each move length 1 or 2) that covers the line, with first move friend, such that sum of hard bosses in friend moves minimized.
We could also consider DP from the perspective of "skip points" but DP is fine.
However, we must be careful: dp states may be large number but within int.
Now, is there any simplification? Because t up to 2e4, sum n 2e5, so total DP operations O(sum n) = 2e5, which is fine.
Implementation details:
We'll read t, loop test cases, read n, read list a (size n). Use 1-indexing for convenience.
Initialize dp0 = [inf](n+1) for friend's turn (i processed, friend to play next) maybe we defined as dp[i][0] and dp[i][1]. Let's define two arrays: dp_f = [inf](n+1) and dp_y = [inf]*(n+1). dp_f[i] = min cost after i bosses processed, and it's friend's turn. dp_y[i] similarly for your turn.
Set dp_f[0] = 0, dp_y[0] = INF (since game must start with friend, so your turn at start is invalid). Then iterate i from 0 to n-1: if dp_f[i] is not INF: # friend moves: kill 1 if i+1 <= n: cost = dp_f[i] + a[i+1] (since friend kills boss i+1, add if hard) dp_y[i+1] = min(dp_y[i+1], cost) # kill 2 if i+2 <= n: cost = dp_f[i] + a[i+1] + a[i+2] dp_y[i+2] = min(dp_y[i+2], cost) if dp_y[i] is not INF: # you move: kill 1 or 2, no cost if i+1 <= n: cost = dp_y[i] + 0 dp_f[i+1] = min(dp_f[i+1], cost) if i+2 <= n: cost = dp_y[i] + 0 dp_f[i+2] = min(dp_f[i+2], cost)
At the end answer = min(dp_f[n], dp_y[n]).
That's it.
But we need to ensure we handle the case n=1: friend must kill the first boss (since it's his turn). So answer = a[1]. Indeed DP: dp_f[0]=0; friend can kill 1: i=0, i+1=1 -> dp_y[1] = a[1]; then at end answer = min(dp_f[1], dp_y[1]). dp_f[1] maybe INF? Let's see: dp_y[0] INF, so dp_f[1] not set? Actually dp_f[1] could be set from dp_y[0] kill 1? But dp_y[0] INF, so dp_f[1] stays INF. So min = dp_y[1] = a[1]. Works.
If n=1 and a[1]=0, answer 0, correct.
Now test the example:
n=8, a = [1,0,1,1,0,1,1,1] (1-indexed) Compute manually? DP should yield 2.
Now check constraints: sum n ≤ 2e5, t up to 2e4, DP O(n) each.
Edge cases: n large, but fine.
Implementation:
We'll use large INF = 10**9.
But we can also do DP using for loops and updating.
Now, can we do a more memory efficient version? Since each state dp[i] only depends on earlier i, we can simply use two arrays for dp_f and dp_y and fill iteratively.
But careful: The DP transitions from i to i+1 and i+2. If we iterate i from 0 to n-1, we update later indices. This is typical forward DP.
We'll need to initialize arrays of length n+1 with INF.
Pseudo:
for each test: read n read list a (length n) as ints INF = 10**9 dp_f = [INF](n+1) dp_y = [INF](n+1) dp_f[0] = 0 for i in range(n): if dp_f[i] < INF: # friend move 1 if i+1 <= n: new_cost = dp_f[i] + a[i] (wait careful: a indexing? a[i+1] is i+1-th boss (1-indexed). In Python list a indexed from 0. Let's store a as 0-indexed but use positions: a[i] for boss i (0-index). Then positions from 0 to n-1. Then we need to adjust.
Better to use 0-indexed for a: a[0..n-1] correspond to bosses 1..n. In DP, i is number of bosses processed, so next boss index = i (0-indexed). So friend kills boss i (if kill 1) or bosses i and i+1 (if kill 2). So transition cost: if friend, add a[i] for kill 1; add a[i] + a[i+1] for kill 2.
So in loop i from 0 to n-1 (i is processed count). For i = n, loop stops. We'll have:
if dp_f[i] < INF: # kill 1 if i < n: new = dp_f[i] + a[i] # because a[i] is next boss dp_y[i+1] = min(dp_y[i+1], new) # kill 2 if i+1 < n: new = dp_f[i] + a[i] + a[i+1] dp_y[i+2] = min(dp_y[i+2], new)
if dp_y[i] < INF: # you kill 1 if i < n: new = dp_y[i] # no cost dp_f[i+1] = min(dp_f[i+1], new) # kill 2 if i+1 < n: new = dp_y[i] dp_f[i+2] = min(dp_f[i+2], new)
At the end answer = min(dp_f[n], dp_y[n]).
Test n=1: a = [1]. dp_f[0]=0. i=0: dp_f[0] < INF: kill1 -> dp_y[1] = 0+1=1; kill2 not possible. dp_y[0] INF skip. Loop ends. answer = min(dp_f[1], dp_y[1]) = min(INF,1)=1. ok.
Test n=1: a=[0]: dp_y[1]=0 -> answer 0.
Now test example manually with small n to ensure correct.
But wait: there is nuance: In each session, the player can kill one or two bosses. Our DP allows the last move to be either player. But what if we end with dp_f[n]? That means after processing n bosses, it's friend's turn. That means the last kill was made by you (since after your kill, next turn is friend). That is valid. Similarly dp_y[n] means last kill by friend, next turn you. So both valid.
Thus answer min of both.
Now complexity O(n) per test.
But we should also consider whether there's any constraint that the friend's session must use at least one skip point? No, he can kill easy bosses without skip points. So if friend kills an easy boss, cost 0.
Thus DP is correct.
Now confirm with provided examples:
Example1: 8 bosses [1,0,1,1,0,1,1,1]. We'll compute DP manually to verify.
Set up a array indices 0-7.
Initialize dp_f[0]=0, dp_y[0]=inf.
i=0: dp_f[0]=0: kill1: i<8 => dp_y[1] = 0 + a[0]=1 kill2: i+1<8 => dp_y[2] = 0 + a[0]+a[1]=1+0=1 dp_y[0] inf -> skip
Now i=1: dp_f[1]? currently INF (not set yet). dp_y[1]=1 Process dp_y[1]=1: kill1: dp_f[2] = min(inf,1) =1 kill2: i+1=2<8 => dp_f[3] = 1 Process dp_f[1] is INF so skip.
i=2: dp_f[2]=1, dp_y[2]=1 (from earlier? Actually dp_y[2] was set to 1 at i=0 kill2) Process dp_f[2]=1: kill1: i=2<8 => new = 1 + a[2] = 1 + 1 = 2 -> dp_y[3] = min(current dp_y[3]? currently maybe INF? Actually we haven't set dp_y[3] yet? Later we might from other transitions, but initially INF) => dp_y[3] = 2 kill2: i+1=3<8 => new = 1 + a[2]+a[3]= 1+1+1=3 -> dp_y[4] = 3 Process dp_y[2]=1: kill1: dp_f[3] = min(current dp_f[3] =1, 1) => remains 1 kill2: i+1=3<8 => dp_f[4] = min(inf,1) =1
i=3: Current values: dp_f[3] = 1 (from dp_y[1] kill2 and dp_y[2] kill1 maybe keep min =1) dp_y[3] = 2 (from dp_f[2] kill1) Possibly also other updates: dp_y[3] might be updated later. Process dp_f[3]=1: kill1: new = 1 + a[3] = 1+1=2 -> dp_y[4] = min(current dp_y[4]=3,2) => 2 kill2: i+1=4<8 => new = 1 + a[3]+a[4] = 1+1+0=2 -> dp_y[5] = 2 Process dp_y[3]=2: kill1: dp_f[4] = min(current dp_f[4]=1,2) => stays 1 kill2: i+1=4<8 => dp_f[5] = min(inf,2) => 2
i=4: Current: dp_f[4] = 1 dp_y[4] = 2 (from dp_f[3] kill1) Also dp_y[4] maybe other? But min is 2. dp_f[5] = 2, dp_y[5] = 2 Process dp_f[4]=1: kill1: new = 1 + a[4] = 1+0=1 -> dp_y[5] = min(current dp_y[5]=2,1) => 1 kill2: i+1=5<8 => new = 1 + a[4]+a[5] = 1+0+1=2 -> dp_y[6] = 2 Process dp_y[4]=2: kill1: dp_f[5] = min(current dp_f[5]=2,2) => stays 2 kill2: i+1=5<8 => dp_f[6] = 2
i=5: Current: dp_f[5] = 2 dp_y[5] = 1 dp_f[6] = 2, dp_y[6] = 2 Process dp_f[5]=2: kill1: new = 2 + a[5] = 2+1=3 -> dp_y[6] = min(2,3) = 2 kill2: i+1=6<8 => new = 2 + a[5]+a[6] = 2+1+1=4 -> dp_y[7] = 4 Process dp_y[5]=1: kill1: dp_f[6] = min(2,1) => 1 kill2: i+1=6<8 => dp_f[7] = 1
i=6: Current: dp_f[6] = 1 dp_y[6] = 2 dp_f[7] = 1, dp_y[7] = 4 Process dp_f[6]=1: kill1: new = 1 + a[6] = 1+1=2 -> dp_y[7] = min(4,2) => 2 kill2: i+1=7<8 => new = 1 + a[6]+a[7] = 1+1+1=3 -> dp_y[8] = 3 Process dp_y[6]=2: kill1: dp_f[7] = min(1,2) => stays 1 kill2: i+1=7<8 => dp_f[8] = 2
i=7: Current: dp_f[7] = 1 dp_y[7] = 2 dp_f[8] = 2, dp_y[8] = 3 Process dp_f[7]=1: kill1: i<8 => new = 1 + a[7] = 1+1=2 -> dp_y[8] = min(3,2) => 2 kill2: i+1=8? i+1=8, but n=8, i+1 == n? Actually i+1 < n? i=7, i+1=8, n=8 => i+1 == n, so kill2 not allowed because need two bosses: i+1 must be < n (since we need boss i and i+1 indices). Condition: if i+1 < n, then i+2 <= n? Actually for kill2 we need both i and i+1 exist. i is next index? When i=7, next boss index is 7 (the 8th boss). For kill2 we need bosses indices i and i+1 (i+1 =8) but index 8 is out of range (since indices 0..7). So kill2 invalid. Process dp_y[7]=2: kill1: dp_f[8] = min(2,2) => 2 kill2: i+1=8? invalid.
Now i=8 loop doesn't run (i up to n-1=7). After loop, dp_f[8]=2, dp_y[8]=2. So answer min=2. Matches expected.
Now test second example: n=5, a=[1,1,1,1,0] -> expected 2. Let's compute quick: We'll trust DP.
Third: n=7, a=[1,1,1,1,0,0,1] -> expected 2. Fourth: n=6 all ones -> expected 2. Fifth: n=1, a=[1] -> 1. Sixth: n=1, a=[0] -> 0.
Works.
Now we have DP solution.
But note: DP can be simplified further using a greedy? Possibly, but not necessary.
We can implement DP as described. Since sum n <= 2e5, we can allocate fresh lists for each test.
Potential optimization: Use arrays of size n+1 and reset? But we just allocate.
Now check if any nuance about friend using skip point: Each hard boss killed by friend requires one skip point; multiple hard bosses in same session require multiple skip points. So additive cost as done.
Thus DP is correct.
Now we can produce final answer.
But we must be careful: The DP as defined uses a[i] for boss i (0-index). For kill2, add a[i] + a[i+1]. All good.
One more check: The DP initial state: dp_f[0]=0, dp_y[0]=INF. But is it possible that the friend does not play any session? No, because the first session is friend's, so he must kill at least one boss. So it's correct.
Now, can we guarantee that we can always partition? With moves of size 1 or 2, any positive n can be covered because we can always break into ones. So DP always yields a solution. So dp_f[n] and dp_y[n] will be finite.
Now we also should consider that t up to 20000, sum n 200000, so we need to handle many small tests efficiently. DP per test O(n) is fine.
Now code.
We'll implement solve().
Pseudo:
import sys
def solve(): import sys input = sys.stdin.readline t = int(input().strip()) for _ in range(t): n = int(input().strip()) a = list(map(int, input().split())) INF = 10**9 dp_f = [INF](n+1) dp_y = [INF](n+1) dp_f[0] = 0 for i in range(n): # friend's turn if dp_f[i] < INF: # kill one if i < n: cost = dp_f[i] + a[i] if cost < dp_y[i+1]: dp_y[i+1] = cost # kill two if i+1 < n: cost = dp_f[i] + a[i] + a[i+1] if cost < dp_y[i+2]: dp_y[i+2] = cost # your turn if dp_y[i] < INF: # kill one if i < n: cost = dp_y[i] # no addition if cost < dp_f[i+1]: dp_f[i+1] = cost # kill two if i+1 < n: cost = dp_y[i] if cost < dp_f[i+2]: dp_f[i+2] = cost ans = min(dp_f[n], dp_y[n]) print(ans)
if name == "main": solve()
That should work.
But let's double-check for n=0? not possible.
Now consider memory: dp arrays of length n+1, okay.
Edge case: n=2. DP: i=0: friend can kill 1 or 2. If friend kills both: cost = a[0]+a[1]; dp_y[2] = that. If friend kills one: dp_y[1]=a[0]. Then i=1: from dp_y[1], you can kill one (boss index 1) -> dp_f[2] = dp_y[1] = a[0]. So answer min(a[0], a[0]+a[1])? Actually min of dp_f[2] and dp_y[2] = min(a[0], a[0]+a[1]). So it might be better to have friend kill only first and you kill second. That seems plausible: friend uses skip point if first hard, you kill second regardless. So answer = a[0] (since friend only kills first). But is it allowed that friend kills one and you kill one? Yes. So correct.
Now verify: if both are hard: a=[1,1], answer min(1, 2) = 1. So friend kills first (cost 1), you kill second. That yields 1. So minimal skip points =1.
If first easy, second hard: [0,1] -> friend kills first (cost 0) you kill second => answer 0. Indeed friend uses no skip. That matches DP.
If first hard, second easy: [1,0] -> friend kills first cost 1; you kill second => answer 1. Or friend kills both cost 1? Actually if friend kills both, cost = 1+0 =1 also. So answer 1. DP yields min( dp_f[2] from you? Actually from dp_y[1] = 1 -> dp_f[2] =1; dp_y[2] from friend kill both =1 => min=1.
Thus ok.
Now check more complex patterns.
We should also ensure that the DP does not allow friend to skip a session. Since each session must kill at least one boss, our transitions only allow moving 1 or 2 ahead. So friend cannot kill 0.
Now one more nuance: In the problem description, after your friend session, your session begins, then again friend, etc. That means the sessions strictly alternate. That is exactly what we have: after friend's move, it's your turn; after your move, it's friend's turn. The DP enforces that by toggling p.
Thus solution is correct.
But there might be a simpler approach: We could note that the DP can be reduced to a simpler recurrence. But it's fine.
Now verify time: For each test case, loop O(n). With sum n = 2e5, that's trivial.
Now let's produce final answer.
But there might be a catch: The friend can use skip points to kill hard bosses. Are skip points used per boss? Yes.
Now, is there any possibility to "skip" a boss without killing? No.
Thus DP is correct.
Now we can finalize.
However, I realize we could also implement DP with two variables and update iteratively, but using array is fine.
One more thought: The DP could be simplified to a greedy: we want to minimize friend's hard kills, so we might want to assign friend to kill as few bosses as possible, but he must kill at least ceil(k/2?) Actually, given the alternating sessions of 1 or 2, the friend's total number of kills is determined by the partition. Since you can kill up to 2 per your turn, we might aim for friend to kill as few bosses as possible, especially avoiding hard ones. But there might be a more elegant solution: we can think of dynamic programming with two states: dp[i] = minimal skip points used up to i, with last kill by friend or you? Equivalent.
But I'll stick with DP.
Now I'll produce final solution.
Before final, test a random case.
Test n=3: a=[1,1,1]. Possible partitions: Friend first:
- Friend kills 1 (cost 1), you kill 1 (boss2), friend kills 1 (boss3) cost 1 => total 2
- Friend kills 1 (cost1), you kill 2 (boss2,3) cost0, friend then? Actually you kill 2 bosses, then all bosses killed? Wait after you kill 2, total becomes 3, game ends. But sessions: friend kills first, then you kill two. That is allowed because you can kill up to 2. So total cost 1.
- Friend kills 2 (cost2), you kill 1 (boss3) => total 2.
- Friend kills 1, you kill 1, friend kills 1? That's the first partition again.
- Friend kills 2, you kill 1? already covered.
- Friend kills 3? Not allowed, only 1 or 2. So best is friend kills first only (hard), you kill the other two: cost 1. But is it allowed that you kill two bosses in a session? Yes. So minimal skip points =1. DP: Let's compute quickly: dp_f[0]=0 i=0: friend kill1 => dp_y[1]=1; friend kill2 => dp_y[2]=2 i=1: from dp_y[1]=1, you kill1 => dp_f[2]=1; you kill2 => dp_f[3]=1 i=2: from dp_f[2]=1: friend kill1 => dp_y[3]=1+ a[2]=1+1=2; friend kill2? i+1=3? n=3, i+1=3 not < n? Actually i+1=3, n=3 => i+1 < n? 3<3 false, so kill2 not allowed. Also from dp_y[2]=2: you kill1 => dp_f[3]= min(1,2)=1; you kill2? i+1=3? invalid. dp_f[3]=1, dp_y[3]=2 => ans=1. Works.
Now test n=2: a=[1,1] -> best is friend kills first (1), you kill second => cost 1. DP yields dp_f[2]=1, dp_y[2]=2 -> ans 1.
Now test n=4: a=[1,0,1,0]. Possible? friend kills first (1) cost1, you kill two (0,1) cost0, friend kills last (0) cost0 => total1. Or friend kills two (1,0) cost1, you kills two (1,0) cost0 => total1. So minimal 1. DP should get 1.
Now test n=4: a=[1,1,1,1]. Possibilities:
- Friend 1 (cost1), you 2 (1,1) cost0, friend 1 (1) cost1 => total2.
- Friend 1 (1), you 1 (1), friend 1 (1), you 1 (1) cost? Actually friend kills first (1) cost1, you kill second (1) cost0, friend kills third (1) cost1, you kills fourth (1) cost0 => total2.
- Friend 2 (1,1) cost2, you 2 (1,1) cost0 => total2.
- Friend 1, you 1, friend 2? cannot because after you kill 1, friend would have to kill two? Actually order: friend kills first (1), you kills second (1), friend can kill two (third and fourth) cost2 => total3.
- Friend 2, you 1, friend 1? after friend kills two, you kills one (third), friend kills one (fourth) cost? Friend cost from first two =2, then friend kills fourth =1 -> total3? Actually careful: sequence: friend kills two (boss1,2) cost2; you kills one (boss3) cost0; friend then must kill boss4? Actually after you kill boss3, remaining boss4, friend's turn. So friend kills boss4 cost1 => total3. So minimal is 2. But is there a way to get total1? Could friend kill only one hard boss? Suppose friend kills first (1) cost1, you kill two (boss2,3) cost0, friend kills boss4 (1) cost1 => total2. Or friend kills boss2? But friend must start from beginning, can't skip boss1. So friend must kill at least two bosses? Since there are 4 bosses, friend's sessions are first and third if you take one each? Actually with alternating, the number of friend sessions is either ceil(n/2) or floor(n/2)? Let's see: if we always kill 1 each, friend kills bosses 1 and 3 => two hard bosses cost2. If you kill 2 in your turn, friend kills boss 1 only? Pattern: friend kills 1, you kill 2,3? Actually you can kill 2 at your turn, so you kill bosses 2 and 3, friend kills boss 1, then game ends? Wait after you kill bosses 2 and 3, total kills = 3, but there are 4 bosses, so we need another friend turn? Actually sequence: friend kills boss1 (session1). Then you kill bosses 2 and 3 (session2). Now total killed = 3. It's friend's turn again (session3) to kill boss4. So friend also kills boss4. So friend kills bosses 1 and 4 => both hard => cost2. So indeed minimum is 2. So DP yields 2.
Now think about a scenario where friend can avoid some hard bosses by having you take them: friend kills easy ones, you kill hard ones. For instance, a=[0,1,0,1,0,1]. Could we achieve 0? friend must kill at least ceil(n/2)? Not necessarily: friend must start and alternate. The number of friend sessions depends on how many bosses each takes. We can have friend take 1 boss, you take 2, friend take 1, you take 2... Let's count: n=6, possible partitions: friend kills 1, you kill 2, friend kills 1, you kills 2 => friend kills 2 bosses total. friend kills 2, you kill 1, friend kills 2, you kills 1 => friend kills 4 bosses. So minimum friend kills is ceil(n/3)? Actually we want to minimize number of friend kills subject to alternating and each session 1 or 2. This is like we want to maximize the number of bosses you kill while ensuring that after each of your sessions, we still can cover the rest with alternating sessions of 1 or 2. This is essentially DP. So DP is appropriate.
Thus final solution.
Now consider if we could use recursion with memoization? Not needed.
Now implement.
But note: In Python, for large t and sum n, using loops and list allocation each test is fine.
Potential micro-optimizations: Use sys.stdin.read to parse all at once? Not necessary, but maybe faster. But given constraints, it's fine.
Now final answer: Provide explanation and code.
But wait, the problem originally from Codeforces: "Mortal Kombat Tower". There is known solution with DP of two states, but often they also find a greedy: Since you can kill two bosses per turn, you can protect friend from hard bosses. However the DP is safe.
Now check memory: dp arrays of size n+1, where sum n <= 200k, so total memory over all tests not huge.
Now we should also consider if we need to reset DP for each test, we allocate new each time.
Now let's think about possible pitfalls: The indexing of a for kill2: we need to ensure i+1 < n to have a[i+1] valid. In code, we check if i+1 < n before accessing a[i+1]. That's done.
Now ensure that dp_y[i] and dp_f[i] can be INF; we use < INF for check.
Now edge case: n=2 and a = [1,1] we already tested.
Now consider n=200000 with all zeros. Then dp will propagate minimal cost 0. DP will compute O(n). Friend's moves will have cost 0, so dp values remain 0. This is fine.
Now test with all ones: n=200000, dp may compute values up to about n/2? But within INF.
Now what about time: O(2e5) per all tests, trivial.
Now we can output answer as integer.
Now maybe there is a simpler solution: The DP can be optimized to O(1) memory by using rolling variables, but not needed.
But given sum n <= 2e5, we can also implement DP with two arrays of length 2? Actually DP states at i depend only on i-1 and i-2? Let's examine: dp_f[i] depends on dp_y[i-1] and dp_y[i-2]; dp_y[i] depends on dp_f[i-1] and dp_f[i-2]. So we can maintain last two values. But we need to compute all i up to n. But we can compute iteratively with two variables for each type? But easier to use arrays.
Given constraints, arrays are fine.
Now we might be able to reduce to a simpler recurrence: dp[i][0] = min(dp[i-1][1] + a[i], dp[i-2][1] + a[i-1] + a[i])? Actually from transitions: dp_f[i] (cost when it's friend's turn after i bosses) can come from dp_y[i-1] (if you killed 1 at previous step) or dp_y[i-2] (if you killed 2). But we also have dp_y[i] from dp_f[i-1] + a[i] and dp_f[i-2] + a[i-1] + a[i]. So we could compute dp_f and dp_y in a single loop. That's essentially the same.
So code above is fine.
Now we should confirm final answer for sample tests:
Input:
6 8 1 0 1 1 0 1 1 1 5 1 1 1 1 0 7 1 1 1 1 0 0 1 6 1 1 1 1 1 1 1 1 1 0
Our DP yields: 2,2,2,2,1,0. matches.
Now implement solve.
Potential improvement: Use reading of all ints via sys.stdin.buffer.read to speed up, but not needed.
But because t up to 20000, input reading via sys.stdin.readline is fine.
Now I'll produce final answer with explanation.
But the problem statement says "You have to answer t independent test cases." So we need to output each answer on its own line.
Now code.
I'll write it now.
But I notice something: In my DP, I used dp_f[i] meaning after i bosses processed, it's friend's turn. But initial dp_f[0]=0, dp_y[0]=INF. But what about the possibility that the first session could be friend's turn and he kills two bosses? That is covered by transition from i=0 to i=2. Good.
Now verify another scenario: n=2, a=[0,0]. Friend can kill 1 (cost 0) you kill 1 -> dp_f[2] from dp_y[1]? Let's compute: dp_f[0]=0; i=0: friend kill1 -> dp_y[1]=0; friend kill2 -> dp_y[2]=0; i=1: from dp_y[1]=0: you kill1 -> dp_f[2]=0; you kill2 invalid? i+2=3 >2. So dp_f[2]=0, dp_y[2]=0 -> ans 0. Works.
Now ensure that dp_y[0] is INF, no transitions from it. That's correct.
Thus solution stands.
Now consider if we need to treat the case where friend can kill 0? No.
Now we can finalize.
Now let's also think about possible alternative approach: Greedy: we always try to have you kill hard bosses when possible. But DP is safe.
Now I'll produce final answer.
Now there is something: Could we have a DP with only one dimension? For instance, dp[i] = min skip points to kill first i bosses, with the last kill being by friend or you? Actually we can have two states: dp[i][0] = min cost to kill first i bosses and the last boss was killed by friend; dp[i][1] = min cost to kill first i bosses and last boss was killed by you. Then transitions: from dp[i-1][1] (if last was you) then next (i-th) could be killed by friend (single) -> dp[i][0] = dp[i-1][1] + a[i]; from dp[i-2][1] -> dp[i][0] = dp[i-2][1] + a[i-1] + a[i]? But careful: if last kill was by friend, then the previous kills might be by you? Actually the sessions alternate, so if the last kill was by friend, then the previous kill must be by you. So dp[i][0] depends on dp[i-1][1] and dp[i-2][1] (since we can have friend's session of length 1 or 2). Similarly dp[i][1] depends on dp[i-1][0] and dp[i-2][0] (with no addition). Base: dp[0][0]? Actually we need to handle zero bosses. This is similar but may be simpler: final answer = min(dp[n][0], dp[n][1]). However, we also need to handle the first session: it's friend's session, so the first kill must be by friend. That can be enforced by initializing dp[0][1] = 0? Hmm, maybe easier to use the previous DP.
Anyway, our DP is fine.
Now final code.
But wait: there's nuance: The friend's skip point usage is per hard boss killed by friend, even if it's in a session where he kills two bosses, each hard costs one. So additive.
Now think about if there's any possibility to "skip" a boss without using a skip point? No.
Thus code done.
Now test sample:
Input: 6 8 1 0 1 1 0 1 1 1 5 1 1 1 1 0 7 1 1 1 1 0 0 1 6 1 1 1 1 1 1 1 1 1 0
Our DP yields: 2,2,2,2,1,0.
Matches.
Now confirm test case 5: n=1, a=[1] -> answer 1. test case 6: n=1, a=[0] -> 0.
All good.
Now let's consider if there's any tricky case: n=2, a=[1,0] -> friend kill 1 cost1, you kill 1 cost0 -> total1. Could there be better? friend kill both cost1? Actually both cost1 as well. So answer1. DP gives? friend kill1 -> dp_y[1]=1; you kill1 -> dp_f[2]=1; friend kill2 -> dp_y[2]=1; min=1.
n=3 a=[0,0,1] -> friend kill 1: easy, you kill 2? Let's enumerate: friend kills first (0) cost0, you kill second and third (0,1) cost0 -> friend only kills first -> total0. So answer 0. DP: i=0: friend kill1 -> dp_y[1]=0; friend kill2 -> dp_y[2]=0; i=1: from dp_y[1]=0: you kill1 -> dp_f[2]=0; you kill2 -> dp_f[3]=0; i=2: from dp_f[2]=0: friend kill1 -> dp_y[3]=0+ a[2]=1 -> dp_y[3]=1; friend kill2 not allowed; from dp_y[2]=0: you kill1 -> dp_f[3]=0; dp_f[3]=0; dp_y[3]=1 => ans=0. Good.
Now n=4 a=[1,1,0,1]. Could we get 1? Possible: friend kills first (1) cost1, you kill second and third (1,0) cost0, friend kills fourth (1) cost1 -> total2. Or friend kills first and second (1,1) cost2, you kills third and fourth (0,1) cost0 -> total2. Or friend kills first, you kills second, friend kills third, you kills fourth: friend kills first and third -> cost1+0=1? Actually third is 0, so cost1. So total1. That is friend kills first (1), you kill second (1), friend kills third (0), you kills fourth (1). Sequence: friend kills boss1 (1). you kills boss2 (1). friend kills boss3 (0). you kills boss4 (1). total friend cost =1. So answer 1. DP should produce 1.
Let's test quickly with DP: a=[1,1,0,1]; n=4.
Initialize dp_f[0]=0.
i=0: friend kill1 -> dp_y[1]=0+1=1; friend kill2 -> dp_y[2]=0+1+1=2. i=1: dp_f[1]? INF? Actually not set. dp_y[1]=1: you kill1 -> dp_f[2]=1; you kill2 -> dp_f[3]=1. i=2: dp_f[2]=1 (from you kill1), dp_y[2]=2 (from friend kill2). Process dp_f[2]=1: friend kill1 -> dp_y[3]=1 + a[2]=1+0=1; friend kill2 -> if i+1=3 < n => dp_y[4]=1 + a[2]+a[3]=1+0+1=2. Process dp_y[2]=2: you kill1 -> dp_f[3]= min(1,2) remains 1; you kill2 -> dp_f[4]=2. i=3: dp_f[3]=1, dp_y[3]=1. Process dp_f[3]=1: friend kill1 -> dp_y[4]=1+ a[3]=1+1=2 => dp_y[4] was 2, min remains 2; friend kill2 not allowed (i+1=4 not < n). Process dp_y[3]=1: you kill1 -> dp_f[4]= min(2,1)=1; you kill2 not allowed. So final dp_f[4]=1, dp_y[4]=2 => answer 1. Good.
So DP works.
Now I think it's correct.
Now we could also consider a more efficient memory usage by using only two variables for each state? But not needed.
Now consider if there is any possibility of overflow? INF = 10**9 is safe because max cost <= n (since each hard boss can cost at most 1, and friend kills at most n bosses). So n <= 2e5, so INF > 2e5.
Now I'm comfortable.
Now I'll produce final answer.
But I'll also add an optional speed reading.
Implementation:
def solve(): import sys data = sys.stdin.read().split() it = iter(data) t = int(next(it)) out = [] for _ in range(t): n = int(next(it)) a = [int(next(it)) for _ in range(n)] INF = 10**9 dp_f = [INF](n+1) dp_y = [INF](n+1) dp_f[0] = 0 for i in range(n): if dp_f[i] < INF: # friend kills 1 cost = dp_f[i] + a[i] if cost < dp_y[i+1]: dp_y[i+1] = cost # friend kills 2 if i+1 < n: cost2 = dp_f[i] + a[i] + a[i+1] if cost2 < dp_y[i+2]: dp_y[i+2] = cost2 if dp_y[i] < INF: # you kill 1 cost = dp_y[i] if cost < dp_f[i+1]: dp_f[i+1] = cost # you kill 2 if i+1 < n: if cost < dp_f[i+2]: dp_f[i+2] = cost ans = min(dp_f[n], dp_y[n]) out.append(str(ans)) sys.stdout.write("\n".join(out))
This should be fast.
Now I'll produce final answer with explanation.
But I need to check that the DP is correct for all n.
One more test: n=0? not allowed.
Now verify a scenario where n=200000 all 1s: DP should compute answer = ceil(n/3)? Actually we can compute minimal friend cost. Let's think: pattern: friend kills 1, you kill 2, friend kills 1, you kills 2, ... For n=200000, friend kills ceil(n/3)? Actually if we always do pattern (F:1, Y:2), then total per 3 bosses friend kills 1 hard, cost 1 per 3 bosses. So total cost ≈ floor? Actually n=3k: cost = k. n=3k+1: pattern: F1,Y2 -> 3 done, then remaining 1 boss must be killed by friend (since it's friend's turn) => cost k+1. n=3k+2: pattern: F1,Y2 (3), then remaining 2 bosses: it's friend's turn; friend could kill 1 or 2. To minimize cost, friend should kill 1? But then you would kill last? Let's see: after F1,Y2, we have processed 3, friend's turn again. Remaining 2 bosses. Options: friend kills 1 (cost 1) then you kill 1 (cost 0) => total cost k+1. Or friend kills 2 (cost 2) => total cost k+2. So best is k+1. So formula: minimal cost = ceil(n/3) *? Actually for all ones, cost = ceil(n/3) maybe? For n=3k: k; n=3k+1: k+1; n=3k+2: k+1. So that's floor((n+2)/3)? Let's check: floor((n+2)/3) for n=3k => (3k+2)/3 = k + 2/3 floor = k, correct; n=3k+1 => (3k+3)/3 = k+1; n=3k+2 => (3k+4)/3 = k+1 floor = k+1. So yes cost = (n+2)//3? Actually (n+2)//3 gives exactly that: (3k+2)//3 = k; (3k+3)//3 = k+1; (3k+4)//3 = k+1. So for all ones, minimal cost = (n+2)//3. Let's test small: n=1 => (3)//3=1? Actually (1+2)//3=1, matches. n=2 => (4)//3=1, matches earlier we had cost 1 for two ones. n=3 => (5)//3=1, but we earlier reasoned for n=3 all ones, cost = 1? Let's recompute: pattern: friend kills 1, you kill 2 => friend kills boss1 (hard) cost1, you kill boss2&3 (both hard) cost0, total cost1. Yes. So (3+2)//3=5//3=1. Good. n=4 => (6)//3=2, matches we computed cost2 for all ones of length 4. n=5 => (7)//3=2, we can test: maybe minimal 2? Let's check: n=5 all ones. Pattern: friend1, you2, friend1, you1? Actually after friend1 (boss1), you2 (boss2,3), friend1 (boss4), you1 (boss5) => friend kills bosses 1 and 4 cost2. That's 2. Could we do better? friend1, you2, friend2? Not allowed because after you2, friend could kill 2? That would be friend kills boss4 and 5: cost2 as well. So 2. So (5+2)//3=7//3=2. So DP should produce that.
Now for arbitrary a, the DP