E2 for 587 Div3 O(1) solution

Правка ru5, от MrLolthe1st, 2019-09-22 20:20:03

1216E2 - Numerical Sequence (hard version)

Обозначим длину последовательности от 1 до $$$i$$$ как $$$L_{i}$$$, тогда $$$L_{i} = L_{i-1} + DigitSum(i)$$$, где $$$DigitSum(x)$$$ — функция, которая получает количество цифр в числе $$$x$$$. Мы знаем, что каждый раз $$$L_{i}$$$ растет на какое-то число $$$e = DigitSum(i)$$$, при чем это число меняется не так часто — только после того, как $$$i$$$ стало больше $$$9, 99, $$$ и т.д. В таком случае, если мы знаем длину последовательности, которая сейчас росла на $$$e = DigitSum(i)$$$, то как только $$$i$$$ станет больше 9, $$$e$$$ увеличится на 1, больше 99 — на 1, и так далее. В этих точках роста $$$e$$$ мы можем посчитать длину ряда, который у нас уже сейчас есть. Первой точкой в этом ряду будет 0. Далее мы можем воспользоваться формулой: $$$E_{i} = E_{i-1} + i\times{(10^{i} - 10^{i-1})}$$$. Такую таблицу до $$$R$$$ мы можем построить за $$$O(DigitSum(R))$$$ — такую табличку можно предподсчитать до начала обработки запросов, при чем $$$R$$$ будет не более $$$\sqrt{2k}$$$. Доказать это несложно — возьмем худший случай, в котором длина новой прицепляемой последовательности растёт ровно на 1 — в таком случае длина всей последовательности будет равной $$$\frac{n*(n-1)}{2}$$$, в нашем же случае — ситуация будет лучше. Обозначим предподсчитанную последовательность как $$$P$$$. По $$$P$$$ мы можем построить вторую последовательность $$$O$$$, где $$$O_{i}$$$ будет обозначать длину цельной последовательности (той, что 1121231234..), после которой мы будем прицеплять новую последовательность от $$$1$$$ до $$$K$$$, где $$$K = 10^{i}$$$. Первым элементом будет $$$0$$$, для каждого следующего несложно вывести формулу $$$cnt = (10^{i}-10^{i-1}), O_{i}=O_{i-1}+P_{i-1}*cnt+i*\frac{cnt*(cnt+1)}{2}$$$. По данной последовательности $$$O$$$ и заданному $$$k$$$ несложно определить, сколько цифр будет содержать каждый последний элемент прицепляемой к нашей последовательности — $$$O_{i}\leq{k}<{O_{i+1}}$$$.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru7 Русский MrLolthe1st 2019-09-22 20:50:11 0 (опубликовано)
ru6 Русский MrLolthe1st 2019-09-22 20:49:42 1604 Мелкая правка: 's{P_{i}}+i\times{\fr' -> 's{P_{i}}+i \times{\fr'
ru5 Русский MrLolthe1st 2019-09-22 20:20:03 1775 Мелкая правка: ' до для K ww\begin{matrix}\nw\n\end{matrix}' -> ' до для K {x}'
ru4 Русский MrLolthe1st 2019-09-22 19:28:01 11 Мелкая правка: 'до для K \{[]}' -> 'до для K \times 5'
ru3 Русский MrLolthe1st 2019-09-22 19:24:58 9 Мелкая правка: 'и от 1 до \K для K' -> 'и от 1 до для K \{[]}'
ru2 Русский MrLolthe1st 2019-09-22 19:22:32 75
ru1 Русский MrLolthe1st 2019-09-22 19:20:41 45 Первая редакция (сохранено в черновиках)