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.
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

There are no comments at the moment.