Problem J. Jump to number ≡

Statement

The task at hand involves finding the k-th sequentially ordered q-ary number (starting from the 1st),
where the sum of its digits equals n, and its length does not exceed l.

Input format

Four integers are provided in the input data: q, n, l and k.

Output format

The output data should contain the resulting number.

If such a number does not exist or if it exceeds the permissible range,
the output data should remain empty.

Constraints

2 ≤ q ≤ 10, 1 ≤ (n, l) ≤ 4000, 1 ≤ k ≤ 10¹⁸

Sample tests

10 100 12 1

199999999999

2 1 1 2

Explanation

Обозначим за N(i, j) количество всех возможных q-ичных чисел длины i, сумма цифр которых равна j.

Очевидно, что N(1, j) = 1 для всех j = 0, 1, …, q − 1, и равно 0 при остальных значениях j.

Далее рассмотрим произвольное число длины i + 1 с суммой цифр j, которое начинается с цифры d.
У такого числа сумма младших i цифр должна равняться j − d.

Таким образом, можно записать рекуррентное соотношение:
N(i + 1, j) = ∑md = 0N(i, j − d), где m = min(q − 1, j).

Здесь для оптимизации можно воспользоваться методом динамического программирования,
сохраняя все ранее насчитанные значения N(i, j) в двумерной таблице.

Далее рассмотрим восстановление числа по его номеру.

Чтобы получить длину такого числа, выберем наибольшее i, для которого N(i, n) ≤ k.

Найдем наибольшее d для которого s = ∑dt = 0N(i − 1, n − t) ≤ k.

Запишем найденное d в текущую позицию нашего числа,
выполним замену n = n − d, k = k − s,
и перейдем к позиции i − 1.

Примечание

Важным будет отметить то, что в процессе заполнения таблицы значений N(i, j)
у нас могут возникать длинные числа.

Однако здесь их можно легко заменить на любое число,
гарантированно больше k.