Участник:Fomberg/CCDSAP

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.codechef.com/submit/CCDSAP - task https://www.codechef.com/viewsolution/30770881 - solution

 
import sys
input = sys.stdin.readline
from sys import stdin, stdout
from math import ceil    
 
def main():
    for _ in range(int(input())):
        n = int(input())
        s = input().strip()
        if n==1:
            print(0)
            continue
        m = s.count("1")
        j = 1
        pos = [-1]*(m+1)
        for i in range(n):
            if s[i]=="1":
                pos[j] = i+1
                j+=1
            if j>m:
                break
        dp = [[[10**9+7,10**9+7] for i in range(m+1)] for j in range(n+1)]
        for i in range(n+1):
            for j in range(m+1):
                for filled in range(2):
                    if j==0:
                        dp[i][j][filled] = 0
                        continue
                    if j > ceil(i/2):
                        continue
                    if filled==1:
                        dp[i][j][filled] = dp[i-1][j-1][0] + abs(pos[j]-i)
                    else:
                        a = dp[i-1][j][0]
                        b = dp[i-1][j][1]
                        dp[i][j][filled] = min(a,b)
        ans = min(dp[n][m][0], dp[n][m][1])
        if ans==10**9+7:
            print("impossible")
        else:
            print(ans)
 
if __name__ == "__main__":
    main()