Составить арифметическое выражение

Учительница математики попросила школьников составить арифметическое выражение так, чтобы его значение было равно данному числу N, и записать его в тетради. В выражении могут быть использованы натуральные числа, не превосходящие K, операции сложения и умножения, а также скобки. Петя очень не любит писать, и хочет придумать выражение, содержащее как можно меньше символов. Напишите программу, которая поможет ему в этом.

Формат входных данных

В первой строке входных данных содержатся два натуральных числа: N (1 <= N <= 10000) - значение выражения и K (1 <= K <= 10000) - наибольшее число, которое разрешается использовать в выражении.

Формат выходных данных

В единственной строке выведите выражение с данным значением, записывающееся наименьшим возможным количеством символов. Если решений несколько, выведите любое из них.

Примечание

При подсчете длины выражения учитываются все символы: цифры, знаки операций, скобки.

Ограничение по времени: 1 секунда
Ограничение по памяти: 64 MB

0

тут ДП походу, только какая-то больно хитровыделанная ...

я бы сделал так:

раскидал N на простые множители и сгруппировал их таким образом, что произведение было минимальной длины.
если из полученных множителей есть такие что > K, то поменять их на сумму в скобках

получается жадность в купе с дп...

1

Хм, интересно. Попробую.

Добавлено через 6 часов 42 минуты
ы...

Добавлено через 1 час 11 минут
Можете кто ни будь создать эту тему в разделе для экспертов С++ ? У меня ранг не позволяет, а в разделе новичков шанс того что помогут не такой большой...

Добавлено через 1 час 3 минуты
Люди из раздела Python подсказали про динамическое программирование... Типа перебор... Не могу представить себе как эту задачу решать с помощью динамического программирования. Столько всего учесть придется... Да и в лимит по времени не факт что уложусь...

0