抵抗暴力破解的方法的难题？

Question

我买了一张空白DVD，准备录制我最喜欢的电视节目。它附带了20个数字贴纸，每个数字'0'到'9'都有2个。
我觉得给我的新DVD收藏贴上数字标签是个好主意。于是我把'1'的贴纸贴在我录制的第一张DVD上，把剩下的19个贴纸放进了抽屉里。
第二天，我又买了一张空白DVD（又得到了20个新贴纸），录完节目后我给它贴上了'2'。
然后我开始想：这些贴纸什么时候会用完，我就不能再给DVD贴标签了？
用几行Python代码来解决这个问题，不是吗？

你能提供一个合理运行时间的代码来解决这个问题吗？

编辑: 直接暴力破解的方法运行起来会太慢。请改进你的算法，让你的代码在大约一分钟内返回正确答案？

额外加分：如果DVD每个数字有3个贴纸呢？

Answer 1

这里有证明解决方案存在：

假设你最终会遇到21位数字，那么每当你购买和贴标签一个DVD时，你就会失去一个贴纸（(+20) + (-21)）。
到目前为止你积累了多少贴纸都没关系。从现在开始，你的贴纸数量会不断减少，最终你会用完它们。

Answer 2

这是一个旧的解决方案，全新的解决方案快了6亿倍，请看下面的链接。

解决方案：

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:])

Answer 3

这是一个全新的解决方案，比第一个快了6万亿倍。

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

real    0m0.777s
user    0m0.772s
sys 0m0.004s

代码：

cache = {}
def how_many_used(n):
    if n in cache:
        return cache[n]
    result = 0
    if int(n) >= 10:
        if n[0] == '1':
            result += int(n[1:]) + 1
        result += how_many_used(str(int(n[1:])))
        result += how_many_used(str(int(str(int(n[0])-1) + "9"*(len(n) - 1))))
    else:
        result += 1 if n >= '1' else 0
    if n.endswith("9" * (len(n)-0)) or n.endswith("0" * (len(n)-1)):
        cache[n] = result
    return result

def how_many_have(i, stickers):
    return int(i) * stickers

def end_state(i, stickers):
    if i == '':
        return 0
    return how_many_have(i, stickers) - how_many_used(i)

cache2 = {}
def lowest_state(i, stickers):
    if stickers <= 0:
        return end_state(i, stickers)
    if i in ('', '0'):
        return 0
    if (i, stickers) in cache2:
        return cache2[(i, stickers)]

    lowest_candidats = []

    tail9 = '9' * (len(i)-1)
    if i[0] == '1':
        tail = str(int('0'+i[1:]))
        lowest_candidats.append(end_state(str(10**(len(i) - 1)), stickers))
        lowest_candidats.append(lowest_state(tail, stickers - 1) + end_state(str(10**(len(i) - 1)), stickers))
    else:
        tail = str(int(i[0])-1) + tail9
        series = end_state(tail9, stickers)
        if series < 0:
             lowest_candidats.append(lowest_state(str(int('0'+i[1:])), stickers) + end_state(i[0] + '0'*(len(i)-1), stickers))
        lowest_candidats.append(lowest_state(tail, stickers))
    result =  min(lowest_candidats)
    cache2[(i, stickers)] = result
    return result

def solve(stickers):
    i=1
    while lowest_state(str(i), stickers) >= 0:
        i *= 2

    top = i
    bottom = 0
    center = 0

    while top - bottom > 1:
        center = (top + bottom) / 2
        if lowest_state(str(center), stickers) >= 0:
            bottom = center
        else:
            top = center

    if lowest_state(str(top), stickers) >= 0:
        return top
    else:
        return bottom

import sys
sys.setrecursionlimit(sys.getrecursionlimit() * 10)

for i in xrange(10):
    print "%d: %d" % (i, solve(i))