python - 挑战蛮力方法的谜题？

Question

我买了一张空白 DVD 来录制我最喜欢的电视节目。它带有 20 位数字的贴纸。 '0'-'9'各2个。
我认为用数字标记我的新 DVD 收藏是个好主意。我在我的第一张录制的 DVD 上贴上了“1”贴纸，并将剩下的 19 张贴纸放在抽屉里。
第二天我买了另一张空白 DVD(收到 20 张新贴纸)并在录制节目后将其标记为“2”。
然后我开始想:贴纸什么时候用完，我就不能再给 DVD 贴标签了？
几行 Python，不是吗？

您能否提供在合理的运行时解决此问题的代码？

编辑:蛮力只会花费太长时间来运行。请改进您的算法，以便您的代码能够在一分钟内返回正确答案？

额外加分:如果 DVD 附带每个数字 3 个贴纸会怎么样？

Answer 1

这是旧的解决方案，全新的解决方案快了 6 亿倍 is on the bottom .

解决方法:

time { python solution.py; } 
0: 0
1: 199990
2: 1999919999999980
3: 19999199999999919999999970
4: 199991999999999199999999919999999960
5: 1999919999999991999999999199999999919999999950
6: 19999199999999919999999991999999999199999999919999999940
7: 199991999999999199999999919999999991999999999199999999919999999930
8: 1999919999999991999999999199999999919999999991999999999199999999919999999920
9: 19999199999999919999999991999999999199999999919999999991999999999199999999919999999918

real    1m53.493s
user    1m53.183s
sys 0m0.036s

代码:

OPTIMIZE_1 = True # we assum that '1' will run out first (It's easy to prove anyway)

if OPTIMIZE_1:
    NUMBERS = [1]
else:
    NUMBERS = range(10)

def how_many_have(dight, n, stickers):
    return stickers * n

cache = {}
def how_many_used(dight, n):
    if (dight, n) in cache:
        return cache[(dight,n)]
    result = 0
    if dight == "0":
        if OPTIMIZE_1:
            return 0
        else:
            assert(False)
            #TODO
    else:
        if int(n) >= 10:
            if n[0] == dight:
                result += int(n[1:]) + 1
            result += how_many_used(dight, str(int(n[1:])))
            result += how_many_used(dight, str(int(str(int(n[0])-1) + "9"*(len(n) - 1))))
        else:
            result += 1 if n >= dight else 0
    if n.endswith("9" * (len(n)-4)): # '4' constant was pick out based on preformence tests
        cache[(dight, n)] = result
    return result

def best_jump(i, stickers_left):
    no_of_dights = len(str(i))
    return max(1, min(
        stickers_left / no_of_dights,
        10 ** no_of_dights - i - 1,
    ))

def solve(stickers):
    i = 0
    stickers_left = 0
    while stickers_left >= 0:
        i += best_jump(i, stickers_left)

        stickers_left = min(map(
            lambda x: how_many_have(x, i, stickers) - how_many_used(str(x), str(i)),
            NUMBERS
        ))
    return i - 1

for stickers in range(10):
    print '%d: %d' % (stickers, solve(stickers))

证明'1'会先用完:

def(number, position):
    """ when number[position] is const, this function is injection """
    if number[position] > "1":
        return (position, number[:position]+"1"+number[position+1:])
    else:
        return (position, str(int(number[:position])-1)+"1"+number[position+1:])