USACO Berries

USACO 2020 January Contest, Silver¶

Problem 1. Berry Picking¶

http://usaco.org/index.php?page=viewproblem2&cpid=990

In [1]:

# SAMPLE INPUT:
#
# 5 4
# 3 6 8 4 2

In [2]:

fin = open ('berries.in', 'r')
fout = open ('berries.out', 'w')
N,K = map(int, fin.readline().split())
print(N,K)
x = fin.readline().split()
maxB = 0
trees = []
for y in x:
    maxB = max(maxB,int(y))
    trees.append(int(y))
print(trees)
#print(maxB)

5 4
[3, 6, 8, 4, 2]

In [3]:

best = 0
halfK = int(K/2)
for b in range(1,maxB+1):
    bbaskets = 0
    remainders = []
    for i in range(N):
        q,r = divmod(trees[i],b)
        bbaskets += q
        remainders.append(r)
    #print(b,remainders)
    # if you can't fill K/2 baskets with b berries, break out of the brute force loop
    if bbaskets < halfK:
        break
    # if you can fill all K baskets (or more) with b berries, 
    # Bessie gets b*K/2 for this value of b, then continue loop
    if bbaskets >= K:
        best = max(best,b*halfK)
        continue
    # if you reach here, you can fill between K/2 and K baskets with b berries.
    bessie_bbaskets = bbaskets-halfK
    bessie_berries = b*bessie_bbaskets
    
    partial_baskets = min(N,halfK-bessie_bbaskets)
    remainders.sort(reverse=True)
    for x in range(partial_baskets):
        bessie_berries += remainders[x]
    
    best = max(best,bessie_berries)

In [4]:

print(best)
fout.write(str(best)+"\n")
fout.close()

8