Editorial for Zombie Swallows
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
import sys
def is_solution(cmin, cmax, insects, feeding):
food = sum(insects[k] for k,f in enumerate(feeding) if f)
if food < cmin or food > cmax:
return False
return True
def extend_solution(insects, feeding):
if len(feeding) >= len(insects):
return
else:
for t in [True, False]:
yield feeding + [t]
def test(cmax, insects, feeding):
food = sum(insects[k] for k,f in enumerate(feeding) if f)
if food > cmax:
return False
return True
def backtracking(cmin, cmax, insects, feeding):
if is_solution(cmin, cmax, insects, feeding):
return True
else:
for new_feeding in extend_solution(insects, feeding):
if test(cmax, insects, new_feeding):
if backtracking(cmin, cmax, insects, new_feeding):
return True
return False
def problem(cmin, cmax, insects):
if backtracking(cmin, cmax, list(reversed(sorted(insects))), []):
print('Sallow swallow swallows.')
else:
print('Sallow swallow wallows in dust.')
swalows = int(sys.stdin.readline())
for _ in range(swalows):
inp = list(map(int, sys.stdin.readline().split()))
problem(inp[0], inp[1], inp[2:])
Comments