给出一些小数字和大数字,得到所需的数字 - 没有循环

Question

我正在解决Python中的codingbat编码问题.该make_bricks问题定义为:

我们想制作一排长达一英寸的砖块.我们有许多小砖(每块1英寸)和大砖(每块5英寸).如果可以通过从给定的砖块中选择来实现目标,则返回True.这比它看起来有点难,可以在没有任何循环的情况下完成.

make_bricks(3, 1, 8) ? True
make_bricks(3, 1, 9) ? False
make_bricks(3, 2, 10) ? True

我想出的第一个解决方案是:

from itertools import permutations

def make_bricks(small, big, goal):
    l = small*[1]+big*[5]
    return any([(goal in i) for i in ([[sum(j) for j in set(permutations(l,i))] \
    for i in range(2,len(l)+1)])])

这是正确的,但被评判软件拒绝,因为不允许进口.我的下一个解决方案是:

def make_bricks(small, big, goal):
    bricks = small*[1]+big*[5]
    for step in range(len(bricks)+1,1,-1):
        for start in range(len(bricks)):
            if len(bricks[start:start+step])==step:
                if sum(bricks[start:start+step])==goal:
                    return True
    return False

哪个也是正确的,但在输入时会因为超时而窒息make_bricks(1000000, 1000, 1000100).

那么,如果不使用导入,不使用循环并在时间限制内,您将如何在Python中解决此问题？

Answer 1

def make_bricks(small, big, goal):
  if goal > small + big * 5:
    return False
  else:
    return goal % 5 <= small

Answer 2

这是一个数学问题.假设你有S小砖块和B大砖块,你想要一个长度L块.

您可以使用K = min(B, L div 5)大砖块和L - 5K小砖块,因此您只需要检查是否有足够的小砖块.

div 是整数除法(floor).

编辑改L-K到L-5K.错字.