Все задачи
Средне Решено: 0 Процент решений: 0%

Цифры константы Чемперноуна

Найдите цифры на заданных позициях строки 123456789101112..., составленной из натуральных чисел подряд.

Чему вы научитесь

  • Считать цифры, занятые числами каждой длины
  • Находить число и цифру по позиции
  • Безопасно работать с 64-битной арифметикой

Условие

Выпишите натуральные числа подряд: 123456789101112131415... На позиции 1 стоит 1, на позиции 10 стоит единица из числа 10, на позиции 11 стоит ноль из числа 10. Для каждой запрошенной позиции найдите стоящую там цифру. Позиции бывают настолько большими, что строку такой длины не построить. Пропускайте целые блоки чисел с одинаковым количеством цифр (9 однозначных чисел, 90 двузначных, 900 трёхзначных, ...).

Реализуйте champernowne_digits(positions).

Входные данные

positions: позиции в строке цифр, считая с 1.

Выходные данные

Верните цифру на каждой позиции в том же порядке, что и во входных данных. Для пустого входа верните пустой список.

Ограничения

0 ≤ positions.length ≤ 100; 1 ≤ position ≤ 10^15

Примеры

Пример 1
Ввод:
positions = [1, 9, 10, 11]

Ожидаемый вывод:
expected = [1, 9, 1, 0]
Ввод:
std::vector<long long> positions = {1, 9, 10, 11};

Ожидаемый вывод:
std::vector<long long> expected = {1, 9, 1, 0};
Ввод:
long[] positions = new long[] {1, 9, 10, 11};

Ожидаемый вывод:
long[] expected = new long[] {1, 9, 1, 0};

Пояснение

Строка начинается с 1 2 3 4 5 6 7 8 9 1 0 1 1, поэтому цифры равны [1, 9, 1, 0].

Пример 2
Ввод:
positions = [15, 190]

Ожидаемый вывод:
expected = [2, 1]
Ввод:
std::vector<long long> positions = {15, 190};

Ожидаемый вывод:
std::vector<long long> expected = {2, 1};
Ввод:
long[] positions = new long[] {15, 190};

Ожидаемый вывод:
long[] expected = new long[] {2, 1};

Пояснение

Позиция 15 - это двойка из числа 12. Позиции с 10 по 189 занимают числа от 10 до 99, поэтому на позиции 190 стоит первая цифра числа 100: [2, 1].

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Числа из d цифр занимают в сумме 9 × 10^(d − 1) × d позиций.

Подсказка 2

Вычитайте целые блоки, пока позиция не окажется внутри одного из них.

Подсказка 3

Внутри блока (позиция − 1) / d показывает, какое это число, а (позиция − 1) % d показывает, какая это цифра.

Ожидаемая сложность

время O(m × log P) для m позиций, доп. память O(m)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.