Задача E. Обучение
Задачу добавил: alef
Успешно сдано решений: 3
Чтобы сотрудники фирмы быстрее освоили новые программные продукты, руководство фирмы решило организовать обучение. Мнения сотрудников разделились. Часть пожелала, чтобы для них были организованы курсы, другая же часть попросила снабдить их соответствующей справочной и учебной литературой, чтобы разобраться в новых продуктах самостоятельно.Теперь руководство хочет узнать, что обойдется дешевле — заказ курсов, закупка книг или же какое-то сочетание того и другого. Дело в том, что и на курсы, и на книги при оптовых и крупнооптовых заказах действуют скидки. Кроме того, руководство полагает, что сможет убедить (всех или частично) заказавших литературу пройти вместо этого обучение на курсах, а пожелавших обучиться на курсах — самостоятельно изучить литературу.
Ваша задача — определить наиболее дешевый вариант для каждого из программных продуктов.
Формат входного файла input.txt
Первая строка — целое число N (1 <= N <= 75000) – количество программных продуктов, для которых требуется определить наилучший вариант
Далее следует N групп, каждая из которых содержит три строки.
Первая строка в группе #j содержит целое число Sj (1 <= Sj <= 2000) – количество сотрудников, которым необходимо овладеть программным продуктом #j
Вторая строка в группе содержит целые числа Lj, Cj, Gj, Aj, Qj, Bj через пробел, где Lj — максимальная наполняемость группы (1 <= Lj <= 2000), Cj (1 <= Cj <= 10000) – стоимость курса обучения для одного человека в группе, если количество групп меньше Gj (1 <= Gj < 1000), Aj (1 <= Aj <= 10000) — стоимость курса обучения для одного человека в группе, если количество групп не меньше Gj, но меньше Qj (Gj < Qj <= 1000), Bj (1 <= Bj <= 10000) — стоимость курса обучения для одного человека в группе, если количество групп не меньше Qj.
Третья строка в группе содержит целые числа Mj, Fj, Xj, Tj, Yj через пробел, где Mj (1 <= Mj <= 10000) — стоимость необходимой литературы при покупке от одного до Fj-1 (1 <= Fj < 1000) экземпляра, Xj (1 <= Xj <= 10000) – стоимость необходимой литературы при покупке от Fj до Tj-1 (Fj < Tj <= 1000) экземпляра, и Yj (1 <= Yj <= 10000) — стоимость необходимой литературы при покупке Tj и более экземпляров.
Группы на курсах должны быть максимально наполненными (за исключением, быть может, одной – последней или единственной).
Формат выходного файла output.txt
В каждой из N строк выходного файла содержится по три целых числа — Kj, Rj, Pj, где Kj – общая стоимость обучения сотрудников соответствующему программному продукту (#j), Rj — количество учебных групп, Pj – количество комплектов литературы.
Если существует более одного ответа для некоторого программного продукта, выведите любой.
Пример входного файла
1
22
7 10 2 8 3 9
15 5 10 15 12
Пример выходного файла
192 2 8