Решение Проекта Эйлера # 305

Question

Задача № 305

Давайте назовем S (бесконечной) строкой что сделано путем объединения последовательные натуральные числа (начиная с 1) записано в базе 10.

Таким образом, S = 1234567891011121314151617181920212223242 ...

Легко видеть, что любое число будет показывать бесконечное количество раз в S.

Давайте назовем f (n) стартовой позицией n-го вхождения n в S. Для Например, f (1) = 1, f (5) = 81, f (12) = 271 и f (7780) = 111111365.

Найти суммирование [f (3 ^ k)] для 1 <= k <= 13. </p>

Как мне решить эту проблему?

Answer 1

Рассчитать S до произвольного размера обманчиво легко, но, как вы, наверное, уже поняли, это непрактично, просто он становится слишком большим.

Как обычно для новых задач Project Euler, грубая сила просто не работает.

Тем не менее, вы все равно можете посмотреть на S для небольших значений k и, возможно, построить формулу, которая решит проблему по частям (первые несколько значений легко обрабатываются в памяти). Кроме того, посмотрите на проблему 40

Примечание: помните правило одной минуты. (большинство проблем можно решить за несколько миллисекунд)

Answer 2

Моя оценка времени работы O (n ² log n), поэтому этот метод грубой силы неосуществим.

Обратите внимание, что вы должны решать проблемы Project Euler самостоятельноИМХО, в частности, относится к новым проблемам.