Загадка, которая игнорирует метод решения "в лоб"?

Результаты для любой базы 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 и будет S новых наклеек на цифру для каждого DVD.

На DVD №X будут полностью наклейки размером X × S «1», независимо от того, использовались они или нет.

Количество используемых наклеек «1» - это просто количество «1» в цифрах от 1 до X в расширении с основанием N.

Таким образом, нам просто нужно найти точку пересечения 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: 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;
}

вот быстрый и грязный сценарий 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}

Вот некоторые мысли по поводу верхней границы, продемонстрированной @Tal Weiss:

Первое 21-значное число равно 10^20, в этот момент у нас будет максимум 20 * 10^20 наклеек. Каждый последующий DVD будет стоить нам как минимум 1 чистую наклейку, так что мы определенно исчерпаем 10^20 + 20 * 10^20, что равно 21 * 10^20. Таким образом, это верхняя граница решения. (Ни в коем случае не особенно жесткая верхняя граница! Но ее легко установить).

Обобщая вышеприведенный результат на базу b:

• каждый DVD поставляется с 2b наклейками
• первый DVD, который стоит нам 1 чистую наклейку - это номер b ^ (2b), и в этот момент у нас будет максимум 2b . b ^ (2b) наклеек
• так что мы обязательно исчерпаем их на b ^ (2b) + 2b . [b ^ (2b)], что равно (2b + 1)[b ^ (2b)]

Так, например, если мы работаем по основанию 3, то этот расчет дает верхнюю границу 5103; по основанию 4 - 589824. Это числа, которые будет гораздо проще перебрать/математически решить.

Это старое решение, совершенно новое решение в 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:])

Вот доказательство того, что решение существует:

Предполагая, что вы когда-нибудь доберетесь до 21 цифры, вы начнете терять наклейку с каждым DVD, который вы покупаете и метите ((+20) + (-21)).
Не имеет значения, сколько наклеек вы накопили до этого момента. С этого момента все идет под откос для вашего тайника, и вы в конечном итоге иссякнете.