Максимальная сумма
Сумма цифр числа и сортировка массива
У Васи есть n карточек, на каждой из которых написано по одному целому числу от 1 до n. Каждое из чисел от 1 до n написано ровно на одной карточке. Например, если n = 4, то у Васи есть одна карточка, на которой написано число 1, одна карточка, на которой написано число 2, одна карточка, на которой написано число 3, и одна карточка, на которой написано число 4.
Вася решил оставить у себя ровно k карточек, а остальные подарить своей подруге. При этом он хочет оставить у себя такие карточки, что сумма цифр всех чисел, написанных на них, была максимально возможной. Например, если n = 20 и Вася оставит у себя три карточки, на которых написаны числа 20, 15 и 7, то сумма цифр будет равна 2 + 0 + 1 + 5 + 7 = 15.
Определите числа, которые должны быть написаны на тех карточках, которые Вася должен оставить у себя.
Входные данные
В первой строке следует целое число n (2 <= n <= 1000) — количество карточек, которые изначально есть у Васи. Во второй строке следует целое число k (1 <= k <= n - 1) — количество карточек, которые Вася хочет оставить у себя.
Выходные данные
В первую строку выведите максимальную сумму цифр всех чисел, которые написаны на k карточках, которые Вася должен оставить у себя.
Во вторую строку выведите k целых чисел через пробел — числа, которые должны быть написаны на карточках,которые Вася должен оставить у себя. Каждое из оставленных чисел должно быть выведено ровно один раз. Числа могут быть выведены в произвольном порядке. Если ответов несколько, разрешается вывести любой из них.
АЛГОРИТМ
- Создаем два массива:
1.1 Основной, содержащий карточки (!!!при этом номер карточки на 1 больше, чем индекс элемента)
1.2 Вспомогательный, по размеру как основной, будет содержать сумму цифр числа на соответствующей карточке
- В цикле заполняем вспомогательный массив.
- Сортируем массив 2 по возрастанию, причем синхронно меняем элементы местави в основном массиве, таким образом, отсортируются карточки в порядке возрастания суммы цифр чисел, записанных на них
- Используя последние k карточки из отстортированных массивов, выводим результат
