Дано n, k. Есть набор из чисел от 1 до n. w(i) — Сумма цифр числа i. Возьмем набор и отсортируем его по следующему правилу: i стоит раньше j, если w(i) < w(j), или если w(i) = w(j) и i лексикографически меньше j. Надо найти k-ый элемент из отсортированного набора и позицию числа k.
Входные Данные: k <= n <= 10^18 Выходные Данные: Нужно вывести k-ый элемент и позицию числа k.
Заранее Спасибо.
позиция числа k : посчитаем такую динамику : dp[j][k], где j — c какой цифры начинается число, k — сумма цифр в числах, пересчет за 10 действий; теперь найдем из динамики кол-во чисел с суммой, меньшей нашего числа k, теперь будем просто перебирать цифры нашего числа и добавим все которые лексикографически меньше (это у которых та же сумма).
Спасибо большое.
Перебирать цифры числа имею ввиду, пусть сумма числа sum, а первая цифра j, тогда прибавим все такие i<j : dp[i][sum-i] и перейдем к след цифре искомого числа