Digital Evolution Foundation#12825

Digital Evolution Foundation (Розбір)

Вікторія Ковальова

Розглянемо функції і : —  кількість чисел з цифр, перша цифра яких не нуль, які мають принаймні один нуль і два нулі не йдуть послідовно, — кількість чисел з цифр, які не мають нулів. g(k) = 9^k

Виразимо значення рекурсивно: Для чисел, що рахує , є варіантів вибору першої цифри. Якщо друга цифра не нуль, то існує f(k - 1) способів вибрати останні k - 1 цифр. Інакше, друга цифра — нуль і існує f(k - 2) варіантів вибору останніх k - 2 цифр.

Отже, f(k) = 9 \cdot (f(k - 1) + f (k - 2)), \text{ при } 2 \leq k.

Знайдемо значення та для k \leq 14. Це можна зробити динамічно за .

Тепер будемо по черзі знаходити цифри -го ідентіфікаційного номеру. Нехай ми знаходимо -ту цифру. Спочатку візьмемо 0 (або 1, якщо це перша цифра чи попередня була 0) та будемо збільшувати її поки можливо. При збільшенні цифри з до x + 1 ми пропускаємо ідентіфикаційні номери, що мали на -й позиції. Кількість таких номерів:

При x = 0: f(15 - i)\text{ (якщо в суфіксі є нулі) }+ g(15 - i) (якщо нема).

При x \neq 0:

номерів з i + 1-ою цифрою не нуль, але з нулями в суфіксі — f(15 - i),

номерів з i + 1-ою цифрою нуль — f(14 - i) + g(14 - i) (їх потрібно враховувати, якщо - не остання),

номерів без нулів в суфіксі — g(15 - i) (їх потрібно враховувати, якщо серед попередніх цифр були нулі).

Позначимо кількість вже пропущенних ідентіфикаційні номерів як . Будемо збільшувати дану цифру, пока вона менша та поки збільшення не призведе до n \leq m. Після того, як ми знайшли всі цифри числа, виведемо його, якщо m + 1 = n, та в іншому випадку.

Ми перебираємо не більше цифр для позицій, тобто асимптотика O(10 \cdot 15) = O(C).