Подсчитайте целые числа до n, которые содержат цифры 2018 по порядку

Если задано целое число n от 0 до 10,0000,0000, посчитайте количество целых чисел, меньших, чем n, которые содержат цифры [2,0,1,8] по порядку.

Так, например, число 9,230,414,587 следует считать, потому что удаление цифр [9,3,4,4,5,7] оставляет нас с [2,0,1,8].

Пример ввода и вывода:

n = 2018      ->  count =     1
n = 20182018  ->  count = 92237

Моя общая мысль такова: максимальная длина n равна 10, а худшая ситуация заключается в том, что мы должны вставить 6 цифр в [2,0,1,8] и удалить дубликаты и числа, превышающие n.

Источник

2 ответа

Решение

Я не вижу каких-либо собственных попыток решить, поэтому я дам только подсказку:

У вас есть 9-значный номер (маленькие цифры могут быть представлены как 000002018), содержащий последовательность цифр 2,0,1,8.
Назовите их "хорошие".
Обозначим цифры от 1 до 9 справа налево:

     number     532705183
digits     5  3  2  7  0  5  1  8  3
index      9  8  7  6  5  4  3  2  1

Самая левая цифра "2" может занимать места от 4 до 9. Сколько хороших чисел содержит первое 2 на k-м месте? Позвольте сделать функцию F2(l, k) для количества хороших чисел, где 2 относится к цифре 2, l - длина номера, k - место для самой левой цифры.

 .   .   .   .  2   .   .   .   .
                ^ 
                | 
 left part      k     right part should contain 0 1 8 sequence
 without 2's

 F2(9, k) = 9^(9-k) * Sum(F0(k-1, j) for j=1..k-1)

Общее количество хороших чисел является суммой F2(9, k) для всех возможных к.

GoodCount = Sum(F2(9, k) for k=4..9)

Объяснение:

Слева 9-мест. Мы можем поставить любую цифру, кроме 2, так что осталось 9^(9-k) возможных левых частей.

Теперь мы можем разместить 0 в правой части и подсчитать возможные варианты для 018 подпоследовательности. F0(...) конечно будет зависеть от F1(...) а также F1 будет зависеть от F8(...) для более коротких номеров.

Поэтому заполните таблицы для значений для F8, F0, F1 пошагово и, наконец, рассчитать результат для цифры 2.

Ручной пример для 4-значных чисел, содержащих подпоследовательность 1 8 а также k = позиция первого '1':
k = 2: есть 81 число добрых xx18
k=3: есть номера вида x1x8 а также x18x
9 таких номеров, как x8, 10 номеров 8x(10 + 9) * 9 = 171
k = 4: есть числа вида
1xx8 (9*9=81 таких номеров),
1x8x (9 * 10 = 90 номеров),
18xx (100 номеров),
итак, 81+90+100=271
Всего: 81+171+271=523

Источник

Это на самом деле сравнительно небольшой набор проблем. Если бы числа были намного больше, я бы предпочел использовать оптимизированные методы, чтобы просто генерировать все числа, которые соответствуют вашим критериям (те, которые содержат цифры в этом порядке), а не генерировать все возможные числа и проверять каждое из них, чтобы убедиться, что оно соответствует критериям.

Тем не менее, метод грубой силы делает ваш 20182018 вариант примерно за десять секунд и полный 1,000,000,000 Диапазон чуть менее восьми минут.

Так что, если вам это не нужно быстрее, вы можете найти метод грубой силы более чем адекватным:

import re

num = 1000000000 # or 20182018 or something else.

lookfor = re.compile("2.*0.*1.*8")
count = 0
for i in range(num + 1):
    if lookfor.search(str(i)) is not None:
        count += 1
        #print(count, i) # For checking.
print(count)
Источник
Другие вопросы по тегам