НачалоПодразделы
Другие разделы
Дата и время
20/12/2024 13:14:50
Занятие 9
F. Гномья нумерация
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 06/11/2007 | Отборочные и районно-городские командные соревнования (D) |
| 07/11/2007 | Занятие 9 (F) |
| 08/07/2019 | Лето 2019 - 4 (D) |
| 23/02/2023 | Базовый уровень: динамическое программирование 1 (проводит BOGAT) (B) |
| 27/02/2024 | Динамическое программирование 1 (проводит BOGAT) (B) |
Ограничения: время – 2s/5s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (6) 
Хотя в основе системы нумерации у гномов лежит число 10, гномы для представления больших чисел используют не десятки, сотни, тысячи, а представляют числа в виде суммы слагаемых, состоящих из одинаковых цифр. Гномы используют 54 слагаемых, а именно 1, 2, …, 9, 11, 22, …, 99, 111, …, 999, 1111, …, 9999, 11111, …, 99999, 111111, …, 999999. Для каждого слагаемого в языке гномов существует особое название и обозначение в виде одной из букв алфавита. Числа в этой системе нумерации можно записать несколькими способами, и гном Док решил найти наиболее компактное представление для записи всех чисел от 1 до 1000000.
Напишите программу, которая для заданного числа найдет его представление в виде суммы минимального числа слагаемых из одинаковых цифр.
Ввод содержит целое число `N` (`1\ ≤\ N\ ≤\ 10^6`).
Вывести число `N`, затем символ '=', затем представление числа `N` в виде суммы гномьих слагаемых. Количество слагаемых в сумме должно быть минимально. Слагаемые могут повторяться, порядок слагаемых в сумме не важен.
Пример ввода
150
Пример вывода
150=111+6+33
