Попробуйте решить одну из задач из прошлых контестов и проверьте свои силы.
Композиция мозаик
Гуляя по туристическим местам, Вы увидели в сувенирном магазине интересную игру, где надо из небольших фрагментов собирать мозаику. Каждый фрагмент промаркирован цифрой от 0 до 9.
Вы закупили их огромное количество. Таким образом, можно считать, что экземпляров каждого фрагмента у вас бесконечное множество.
Добравшись до отеля, Вы решили собрать k красивых мозаик, каждая из которых представляет собой некоторое количество фрагментов, выложенных в ряд.
Мозаика считается красивой, если число, образованное цифрами с фрагментов мозаики, не содержит лидирующих нулей. Красотой
мозаики является число, полученное путём последовательного выписывания цифр соответствующих фрагментов в десятичное число.
Собрав множество красивых мозаик, Вы решили объединить их в композицию и выложили их в один ряд. Красотой композиции решили считать число, полученное выписыванием цифр всех фрагментов мозаик.
В этот момент Вы задались вопросом, какую максимальную красоту композиции вы можете получить из мозаик, сумма красоты которых равна n.
Формат входных данных
Единственная строка входных данных содержит два целых числа
1 ≤ n ≤ 10³⁰⁰⁰, 1 ≤ k ≤ 2000 — сумма красот мозаик и число мозаик в композиции, соответственно.
Формат выходных данных
В единственной строке выведите k целых чисел, разделённых пробелом — значения красот мозаик, входящих в композицию, расположенных слева направо в композиции с максимальной
красотой.
Регистрация на Yandex Cup
▪️▪️▪️▪️▪️▪️▪️▪️
Algorithm: a problem from a previous Yandex Cup
Try solving one of the problems from previous contests and see how you do.
Composition of Mosaics
While walking through tourist spots, you saw an interesting game in a souvenir shop where you have to assemble a mosaic from small fragments. Each fragment is marked with a digit from 0 to 9.
You bought a huge number of them. Thus, you can consider that you have an infinite supply of each fragment.
Upon reaching the hotel, you decided to assemble k beautiful mosaics, each of which consists of a certain number of fragments arranged in a row. A mosaic is considered beautiful if the number formed by the digits of the mosaic fragments does not contain leading zeros. The beauty of the mosaic is the number obtained by sequentially writing down the digits of the corresponding fragments as a decimal number.
After assembling a number of beautiful mosaics, you decided to combine them into a composition and arrange them in a single row. The beauty of the composition is defined as the number obtained by writing down the digits of all the fragments of the mosaics.
At this point, you wondered what the maximum beauty of the composition you can achieve from mosaics, the sum of the beauties of which equals n.
Input
The only input line contains two integers 1 ≤ n ≤ 10³⁰⁰⁰, 1 ≤ k ≤ 2000 — the sum of the beauties of the mosaics and the number of mosaics in the composition, respectively.
Output
In a single line, output k integers separated by spaces — the values of the beauties of the mosaics that are part of the composition, arranged from left to right in the composition with maximum beauty.
Yandex Cup registration