Форум » Обработка числовых последовательностей » [C4] Задача про плотника Ивана » Ответить
[C4] Задача про плотника Ивана
tavabar: Недавно эту задачу опубликовали вконтакте. Говорят, кто её сможет решить, тот готов к егэ =). Это какая тема проверяется? Как решать такую задачу: Плотник Иван получил N заказов. Просматривая заказы он заметил, что для их выполнения нехватает M станков. Однако есть заказы, не требующие всех станков для выполнения, но каждый заказ требует хотя бы один из них. Иван может либо заказать, либо купить станок для выполнения заказа. Т.к. на каждый заказ требует разный объем работ, значит и разное время работы на станке, так что стоимость аренды может зависеть от работы, выполняемой на станке. Стоимость покупки никак не зависит от выполняемых на этом станке работ. Купленный станок может быть использован для любого количества работ бесплатно. Если Ивану стоимость выполнения заказа кажется слишком высокой, то он может отказаться от него. Напишите программу, которая поможет Ивану понять от какого заказа отказаться и какие станки купить, что бы максимизировать свой доход. Пример: N=2 M=3 Заказы: Доход от O1 100 Доход от O2 100 Станки (стоимость покупки): M1 50 M2 80 M3 110 Для заказа O1 требуются станки M1 и M2 с ценами за аренду в 30 и 20 соотв. Для заказа O2 требуются станки M1 и M3 с ценами за аренду 40 и 80 соответственно. Здесь два решения, ведущие к максимальному доходу в 50: Отказаться от O2, завершить O1. Арендовать M1, M2. Завершить оба O1 и O2. Купить M1, арендовать M2 и M3. На вход программе подается 2 числа N (1<=N<=1200) и M (1<=M<=1200). Следующие N блоков строк описывают заказы. Блоки состоят из: Первая строка блока i содержит 2 числа доход от завершения Vi (1<=Vi<=5000) заказа Oi и количество станков mi (1<=mi<=M) необходимых для выполнения заказа Oi. Следующие mi строк описывают станки. Строки состоят из: номера станка j (1<=j<=M) необходимого для завершения заказа и стоимости аренды Rij (1<=Rij<=20000) станка j для выполнения заказа i. Следующие M строк содержат по одному числу - стоимости покупки i-го станка Si (1<=Si<=20000). Вывести нужно всего одно число - максимальных доход. Пример: Входной файл: 2 3 100 2 1 30 2 20 100 2 1 40 3 80 50 80 110 Выходной файл: 50
Ответов - 1
Поляков: Это олимпиадная задача на оптимизацию, на ЕГЭ таких не будет.
полная версия страницы