Healthy Holsteins (USACO Training Problem)¶
In [ ]:
## holstein.in contains the following data
"""
4
100 200 300 400
3
50 50 50 50
200 300 200 300
900 150 389 399
"""
In [1]:
"""
ID: karihee1
LANG: PYTHON3
TASK: holstein
"""
import itertools
fin = open ('holstein.in', 'r')
fout = open ('holstein.out', 'w')
V = int(fin.readline().strip())
requirements = [x for x in map(int,fin.readline().split())]
G = int(fin.readline().strip())
feedvitamins = list()
for i in range(G):
tempv = [x for x in map(int,fin.readline().split())]
feedvitamins.append(tempv)
In [2]:
def checkDiet(v,r,g,f,s):
feedindexes = [x for x in range(g)]
for config in itertools.combinations(feedindexes,s):
#print(config)
diet = [0]*v
for i in config:
for j in range(v):
diet[j] += f[i][j]
bads = 0
for j in range(v):
if diet[j]<r[j]:
bads+=1
break
if bads>0:
continue
else:
#print("found a good diet")
return config
config = tuple() # return empty tuple if no good diet found
return config
In [3]:
def checkDiet(v,r,g,f,s):
feedindexes = [x for x in range(g)]
for config in itertools.combinations(feedindexes,s):
#print(config)
diet = [0]*v
for i in config:
for j in range(v):
diet[j] += f[i][j]
bads = 0
for j in range(v):
if diet[j]<r[j]:
bads+=1
break
if bads>0:
continue
else:
#print("found a good diet")
return config
config = tuple() # return empty tuple if no good diet found
return config
In [4]:
for S in range(1,G+1):
ans=checkDiet(V,requirements,G,feedvitamins,S)
if len(ans)>0:
break
print("Min Scoops:",len(ans))
print("Feeds:",ans)
fout.write(str(len(ans)))
for x in ans:
fout.write(" "+str(x+1))
fout.write("\n")
fout.close()
