Greedy Gift Givers

Greedy Gift Givers (USACO Training Problem)¶

In [ ]:

# gift1.in contains the following test data:
"""
5
dave
laura
owen
vick
amr
dave
200 3
laura
owen
vick
owen
500 1
dave
amr
150 2
vick
owen
laura
0 2
amr
vick
vick
0 0
"""

In [1]:

fin = open("gift1.in", "r")

N = int(fin.readline().strip())

names=list()
money=dict()
for counter in range(N):
    tempname = fin.readline().strip()
    names.append(tempname)
    money[tempname]=0

print(N)
print(names)
print(money)

5
['dave', 'laura', 'owen', 'vick', 'amr']
{'dave': 0, 'laura': 0, 'owen': 0, 'vick': 0, 'amr': 0}

In [2]:

for i in range(N):
    Giver = fin.readline().strip()
    Bank, NumGifts = map(int, fin.readline().split())
    money[Giver] -= Bank
    
    if NumGifts > 0:
        Q,R = divmod(Bank,NumGifts)
        money[Giver] += R
        for j in range(NumGifts):
            tempname = fin.readline().strip()
            money[tempname] += Q
    
print(money)    

{'dave': 302, 'laura': 66, 'owen': -359, 'vick': 141, 'amr': -150}

In [3]:

fout = open("gift1.out","w")
for n in names:
    fout.write(n + " " + str(money[n])+"\n")
fout.close()