rounding.py

from math import floor
from bisect import bisect_left
import sys

def rounding(N):
    r = []
    for i in range(1, N):
        if 100 * i/N - floor(100 * i /N) >= 0.5:
            r.append(i)
    return r

def solve(l1, l2, r, remaining):
    #l1 est la liste possiblement a completer
    #l2 est la liste qui arrondit en haut
    if remaining == 0:
        return l1 + l2
    if len(l1) == 0:
        n = remaining // r[0]
        l2.extend([r[0]] * n + [remaining - n])
        return l2
    else:
        e = l1.pop()
        i = bisect_left(r, e)
        if r[i] == e:
            l2.append(e)
            return solve(l1, l2, r, remaining)
        else:
            if r[i] - e > r[0]: # ca sert a rien de completer
                l2.append(e)
                return solve(l1, l2, r, remaining)
            else:
                if r[i] - e <= remaining:
                    l2.append(r[i])
                    return solve(l1, l2, r, remaining + e - r[i])
                else:
                    l1.append(e + remaining)
                    return solve(l2, l1, r, 0)

def score(survey, N):
    r = 0
    for l in survey:
        if (l * 100/N) - floor(l*100/N) >= 0.5:
            r += floor(l*100/N) + 1
        else:
            r += floor(l*100/N)
    return r

if __name__ == "__main__":
    if len(sys.argv) > 1:
        fh = open(sys.argv[1])
    else:
        fh = sys.stdin

    T = int(fh.readline())
    for i in range(T):
        N, L = map(int, fh.readline().split())
        l1 = list(map(int, fh.readline().split()))
        r = rounding(N)
        if len(r) == 0:
            print("Case #{}: {}".format(i + 1, 100))
        else:
            survey = solve(l1, [], r, N - sum(l1))
            print("Case #{}: {}".format(i+1, score(survey, N)))