Оптовая закупка (100 баллов)
Задачу добавил: alef
Успешно сдано решений: 0
Покупать другие материалы для ремонта было решено в торговом центре «Проксима». Мы не будем приводить здесь весь список того, что нужно купить. Скажем лишь, что в этом списке было M различных наименований товаров, и возле каждого наименования было указано, какое количество (единиц) этого товара необходимо приобрести. В торговом центре продаются все M наименований товара. Кроме того, предусмотрено три вида скидок «мелкий опт», «средний опт» и «крупный опт». Такие скидки предоставляются в том случае, если товары принадлежат к одной товарной группе. Если приобретаются товары из одной товарной группы на сумму, превышающую некоторую заранее заданную, то их общая стоимость уменьшается на определенный процент. Разумеется, когда до суммы, с которой можно получить скидку, немного не хватает, покупатель может приобрести какие-то из нужных ему товаров «про запас» – не исключено, что это окажется выгоднее.
Ваша задача – написать программу, позволяющую потратить как можно меньше денег на необходимые покупки
Формат входного файла input.txt
Первая строка – целые числа M, G, S, O1, D, O2, L, O3 через пробел
M – количество наименований товаров, которые необходимо приобрести (1<=M<=30)
G – количество товарных групп (1<=G<=10)
S – скидка (в процентах) предоставляемая при покупке «мелким оптом» – т.е. на сумму, не меньшую O1 (0<=S<100, 1<=O1<=10000)
D – скидка (в процентах) предоставляемая при покупке «средним оптом» – т.е. на сумму, не меньшую O2 (0<=D<100, O1<=O2<=10000)
L – скидка (в процентах) предоставляемая при покупке «крупным оптом» – т.е. на сумму, не меньшую O3 (0<=L<100, O2<=O3<=10000)
Каждая из следующих M строк содержит по три целых числа: Qj, Cj, Fj через пробел
Qj – количество единиц товара № j, которое необходимо приобрести (1<=Qj<=100)
Сj – цена единицы товара № j (1<=Cj<=1000)
Fj – номер товарной группы, к которой принадлежит товар № j (1<=Fj<=G)
(данные по первому товару записаны во второй строке входного файла, и т.д.)
Формат выходного файла output.txt
Первая строка – вещественное число с точностью 2 знака после запятой – минимальная сумма, которая может быть истрачена на покупки
Пример входного файла
5 2 5 1000 7 2000 15 5000
7 266 2
3 55 1
9 180 2
12 10 1
8 168 2
Пример выходного файла
4540.10