Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
MihaniX
 Аватар для MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
19.12.2013, 13:05     Составить арифметическое выражение #1
Учительница математики попросила школьников составить арифметическое выражение так, чтобы его значение было равно данному числу N, и записать его в тетради. В выражении могут быть использованы натуральные числа, не превосходящие K, операции сложения и умножения, а также скобки. Петя очень не любит писать, и хочет придумать выражение, содержащее как можно меньше символов. Напишите программу, которая поможет ему в этом.

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

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

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

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

Примечание

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

Ограничение по времени: 1 секунда
Ограничение по памяти: 64 MB
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.12.2013, 13:05     Составить арифметическое выражение
Посмотрите здесь:

Арифметическое выражение C++
C++ Вычислить арифметическое выражение
C++ [C++] Вычислить арифметическое выражение
C++ Вычислить арифметическое выражение
Записать арифметическое выражение C++
C++ вычислить арифметическое выражение
С++ Вывести арифметическое выражение C++
C++ Арифметическое выражение

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110
19.12.2013, 15:19     Составить арифметическое выражение #2
тут ДП походу, только какая-то больно хитровыделанная ...

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

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

получается жадность в купе с дп...
MihaniX
 Аватар для MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
22.12.2013, 21:43  [ТС]     Составить арифметическое выражение #3
Хм, интересно. Попробую.

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

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

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

Текущее время: 10:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru