Question

Есть последовательность следующего типа: "123112233111222333111122223333...". Найдите его
n
-й элемент.

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

В первой строке входных данных задается одно целое числе (1≤n≤10в 9й степени).

Выходные данные
Выведите одно целое число — ответ на задачу.


Примеры -
--------------------------
входные данные
1
выходные данные
1
--------------------

----------------------
входные данные
5
выходные данные
1
----------------------

-----------------------
входные данные
18
выходные данные
3
-----------------------

Даю 50 балов

Answer 1

Ответ на языке Python:

n = int(input())

n -= 1

d = 1/4. + 2 * n / 3.

k = int(d ** 0.5 - 1/2.)

s = 3 * k + 3 * (k - 1) * k / 2

answer = (n - s) // (k + 1) + 1

print(answer)

Объяснение:

Разделим последовательность на блоки: первый - 123, второй - 112233, третий - 111222333 и т.д. В блоке номер k будет k единиц, k двоек, k троек - всего 3k цифр.

Следующий шаг: понять, сколько целых блоков написано до элемента n. Заметим, что длины блоков увеличиваются на 3 - длина первого 3, длина второго 6, длина третьего 9, длина k-того 3k. То есть длина k блоков - сумма арифметической прогрессии с шагом 3 и первым элементом 3. Сумма вычисляется по известной в школе формуле $S = ka_1 + \frac{d(k-1)k\\}{2}$.

Подставим a_1 (длина первого блока), шаг и запишем в виде квадратного уравнения

$S = \frac{3}{2} k^2 + \frac{3}{2} k$.

Теперь осталось только найти максимально возможное целое k, такое что S <= n. Это равносильно уравнению

$\frac{3}{2} k^2 + \frac{3}{2} k - n \leq 0$.

Решаем квадратное уравнение, получаем, что максимальное к это

$k = [-\frac{1}{2} + \sqrt{\frac{1}{4} + \frac{2}{3}n } ]$. ([ ] - обозначение целой части).

Следует заметить, что для n равных 3, 9, 18, ... (номер последнего элемента блока) будет считаться, что блок уже написан полностью, т.е. для n = 3, мы найдем k = 1, для n = 9 - k = 2, что не очень удобно. Поэтому будем считать, что нумерация элементов начинается с 0, то есть первый блок  - индексы 0, 1, 2, второй - 3, 4, 5, 6, 7, 8 и т.д. Для этого нужно уменьшить n на единицу. Теперь k точно определяет сколько блоков полностью написано до искомого элемента.

Теперь посчитаем по вышенаписанной формуле арифметической прогрессии сумму S - сколько всего элементов написано во всех полных блоках. Тогда n - s = номер искомого элемента в блоке (нумерация с 0). Так как мы находимся в блоке k + 1, то, если n - s < k + 1 - искомый элемент это единица, если n - s < 2(k + 1) - искомый элемент 2, иначе 3. В программе это коротко записано через целочисленное деление.