挑战暴力方法的谜题？

Question

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

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

编辑：暴力破解将需要太长时间来运行。请改进您的算法，以便您的代码在一分钟之内返回正确的答案？

额外加分：如果 DVD 上每个数字都有 3 个贴纸怎么办？

Answer 1

这是旧的解决方案，全新的解决方案速度快了 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 2

这里是存在解决方案的证据：

假设您达到了 21 位数字，您将开始丢失购买的每张 DVD 和标签上的贴纸 ((+20) + (-21))。
到目前为止，您积累了多少贴纸并不重要。从这里开始，你的贴纸收藏就开始走下坡路，你最终会用完。

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

Answer 4

这是一个快速而肮脏的 python 脚本：

#!/bin/env python

disc = 0
stickers = {
    0: 0, 1: 0,
    2: 0, 3: 0,
    4: 0, 5: 0,
    6: 0, 7: 0,
    8: 0, 9: 0 }

def buyDisc():
    global disc
    disc += 1
    for k in stickers.keys():
        stickers[k] += 1

def labelDisc():
    lbl = str(disc)
    for c in lbl:
        if(stickers[int(c)] <= 0): return False;
        stickers[int(c)] -= 1;
    return True

while True:
    buyDisc()
    if not labelDisc(): break

print("No stickers left after " + str(disc) + " discs.")
print("Remaining stickers: " + str(stickers))

但我不知道它是否会产生正确的结果。如果您发现逻辑错误，请使用调试

输出注释结果：

Bought disc 199991. Labels: 
Remaining stickers: {0: 111102, 1: 0, 2: 99992, 3: 99992, 4: 99992, 5: 99997, 6: 99992, 7: 99992, 8: 99992, 9: 100024}

Answer 5

对于任何基数 N 和每张 DVD“S”的每个数字的贴纸数量，结果都是：

N\S ]      1 |        2 |          3 |         4 |    5 |        S?
===================================================================
  2 ]      2 |       14 |         62 |       254 | 1022 |   4^S - 2
----+--------+----------+------------+-----------+------+----------
  3 ]     12 |      363 |       9840 |    265719 |     (27^S - 3)/2
----+--------+----------+------------+-----------+-----------------
  4 ]     28 |     7672 |    1965558 | 503184885 |
----+--------+----------+------------+-----------+
  5 ]    181 |   571865 | 1787099985 |
----+--------+----------+------------+
  6 ]    426 | 19968756 |
----+--------+----------+
  7 ]   3930 | (≥ 2^31) |
----+--------+----------+
  8 ]   8184 |
----+--------+
  9 ] 102780 |
----+--------+
 10 ] 199990 |
----+--------+

我看不到任何图案。

---

或者，如果标签从 0 而不是 1 开始，

N\S ]       1 |        2 |          3 |         4 |    5 |          S?
======================================================================
  2 ]       4 |       20 |         84 |       340 | 1364 | (4^S-1)*4/3
----+---------+----------+------------+-----------+------+------------
  3 ]      12 |      363 |       9840 |    265719 |       (27^S - 3)/2
----+---------+----------+------------+-----------+-------------------
  4 ]      84 |     7764 |    1965652 | 503184980 |
----+---------+----------+------------+-----------+
  5 ]     182 |   571875 | 1787100182 |
----+---------+----------+------------+
  6 ]    1728 | 19970496 |
----+---------+----------+
  7 ]    3931 | (≥ 2^31) |
----+---------+----------+
  8 ]   49152 |
----+---------+
  9 ]  102789 |
----+---------+
 10 ] 1600000 |
----+---------+

---

我们假设是“1”标签先用完 - 对于大多数其他计算信息来说确实是这种情况。

假设我们的基数为 N，每张 DVD 的每个数字都有 S 个新贴纸。

在 DVD #X 中，将总共有 X×S 个“1”贴纸，无论是否使用过。

所使用的“1”贴纸的数量只是N基数扩展中从1到X的数字中“1”的数量。

这样我们只需要找到X×S与总“1”位数的交叉点即可。

• N = 2: 1,2,4,5,7,9,12,13 ,15,17,20,22,25,28,32,33,35,37,40,42,45,48,52,54,57,...
• N = 3: 1,1,2, 4,5,5,6,6,7,9,10,12,15,17,18,20,21,21,22,22,23,25,26,26,27,…
• N = 10: < a href="http://www.research.att.com/~njas/sequences/A094798" rel="nofollow noreferrer">1,1,1,1,1,1,1,1,1,2, 4,5,6,7,8,9,10,11,12,12,13,13,13,13,13,…

所有这些序列似乎都不存在闭集，因此循环比例 X 次迭代是必要的。可以在 log X 时间内提取数字，因此原则上该算法可以在 O(X log X) 时间内完成。

这并不比其他算法更好，但至少可以删除很多计算。 C 代码示例：

#include <stdio.h>

static inline int ones_in_digit(int X, int N) {
    int res = 0;
    while (X) {
        if (X % N == 1)
            ++ res;
        X /= N;
    }
    return res;
}

int main() {
    int N, S, X;

    printf("Base N?   ");
    scanf("%d", &N);
    printf("Stickers? ");
    scanf("%d", &S);

    int count_of_1 = 0;
    X = 0;
    do {
        ++ X;
        count_of_1 += S - ones_in_digit(X, N);
        if (X % 10000000 == 0)
            printf("%d -> %d\n", X/10000000, count_of_1);
    } while (count_of_1 >= 0);
    printf("%d\n", X-1);
    return 0;
}

Answer 6

以下是 @Tal Weiss：

第一个 21 位数字是 10^20，此时我们将最多 20 * 10^20 贴纸。随后的每张 DVD 将花费我们至少 1 个网络贴纸，因此我们肯定会用完 10^20 + 20 * 10^20，这等于 21 * 10^20。因此，这是解的上限。 （无论如何，这不是一个特别严格的上限！但很容易建立）。

将上述结果推广到基 b：

• 每张 DVD 都带有 2b 贴纸，
• 第一张花费我们 1 个净贴纸的 DVD 的编号是 b ^ (2b)，此时我们最多会有 2b 。 b ^ (2b) 贴纸
• ，所以我们肯定会用完 b ^ (2b) + 2b 。 [b ^ (2b)]，等于 (2b + 1)[b ^ (2b)]

因此，例如，如果我们使用基数 3，则此计算给出的上限为5103;以 4 为基数，它是 589824。使用这些数字进行暴力/数学求解会更容易。