Участник:Andriygav/FCANDY

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

https://www.spoj.com/problems/FCANDY/

import numpy as np
 
def solver(N, ks, cs):
    me = 40025
    offset = 20000
 
    bs = np.zeros((N+1, me), dtype=np.bool)
 
    bs[0][offset] = True
 
    for i in range(1, N+1):
        k = ks[i-1]
        c = cs[i-1]
        for j in range(k//2+1):
            d = (k-2*j)*c
            if d < len(bs[i]):
                if d != 0:
                    bs[i][:-d] += bs[i - 1][d:]
                    bs[i][d:] += bs[i - 1][:-d]
                else:
                    bs[i] += bs[i - 1]
                    bs[i]+= bs[i - 1]
 
    result = me
    for i in range(me):
        if bs[N][i]:
            result = min(result, abs(i-offset))
 
    return result
 
ks = []
cs = []
 
N = int(input())
for i in range(N):
    k, c = list(map(int, input().split()))
    ks.append(k)
    cs.append(c)
 
print(solver(N, ks, cs))