e-olymp
Задачі

Градуйований лексикографічний порядок

Градуйований лексикографічний порядок

Розглянемо цілі числа від 1 до n. Назвемо вагою числа його суму цифр, і позначимо вагу числа x як w(x).

Потім упорядкуємо числа у так званому градуйованому лексикографічному порядку. Нехай задано два числа a та b. Якщо w(a) < w(b), то число a йде у градуйованому лексикографічному порядку до числа b. Якщо ж w(a) = w(b), тоді число a йде у градуйованому лексикографічному порядку до числа b якщо і лише якщо десяткове подання числа a лексикографічно менше десятикового подання числа b.

Наприклад, у цьому порядку:

  • число 120 йде до числа 4;
  • число 555 йде до числа 78;
  • число 20 йде до числа 200.

За заданими n і k, знайдіть номер числа k і число, яке знаходиться на k-му місці, у градуйованому лексикографічному упорядкуванні натуральних чисел від 1 до n.

Вхідні дані

У вхідному файлі записані числа n і k (1kn1018).

Вихідні дані

У першому рядку вихідного файлу виведіть номер числа k.

У другому рядку виведіть число, яке знаходиться на k-му місці.

Ліміт часу 3 секунди
Ліміт використання пам'яті 32 MiB
Вхідні дані #1
20
10
Вихідні дані #1
2
14