Сплав из лома
Литейный цех плавит сплав из лома. На складе n видов сырья: про каждый известна цена за килограмм в тенге, сколько его есть и какую долю каждого из k элементов он содержит. Нужно получить ровно M килограммов сплава, в котором доля каждого элемента лежит в заданных пределах. Сырьё можно брать в любых количествах, не больше запаса, в том числе дробных. Какая самая низкая цена партии?
Доля элемента в сплаве — его масса во всём сырье, делённая на M. Остальное в сырье — примеси, на которые ограничений нет.
Вход
В первой строке — n, k, M (1 ≤ n ≤ 60, 1 ≤ k ≤ 10, 1 ≤ M ≤ 105). Дальше n строк: цена p (1 ≤ p ≤ 105), запас s в килограммах (0 ≤ s ≤ 105) и k долей элементов в десятых долях процента (целые от 0 до 1000, их сумма не больше 1000). Дальше k строк: нижняя и верхняя граница доли элемента в сплаве, тоже в десятых долях процента, 0 ≤ lo ≤ hi ≤ 1000.
Выход
Наименьшую цену партии или IMPOSSIBLE, если получить такой сплав из этого сырья нельзя. Ответ засчитывается с ошибкой до 10−6 от ответа (и до 10−6 абсолютной для чисел меньше единицы).
Примеры
Пример 1
3 2 100 4200 100 999 0 1500 100 0 995 2600 100 650 340 600 630 360 400
251538.4615
Пример 2
3 2 100 4200 100 999 0 1500 10 0 995 2600 100 650 340 400 500 500 600
IMPOSSIBLE
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Неизвестные — сколько килограммов взять каждого сырья, x1, …, xn. Масса, доли элементов, запасы и цена — всё это линейные выражения от x. Значит, это линейная задача.
2Подсказка 2
Неравенства нужно превратить в равенства. Для «не больше» добавьте неотрицательную переменную-остаток со знаком плюс, для «не меньше» — с минусом. Тогда задача примет вид A·x = b, x ≥ 0, цена → min, и её решает симплекс-метод в две фазы.
3Идея
Строки: Σxj = M; для каждого сырья xj + sj = запас; для каждого элемента Σ доляj·xj − u = lo·M и Σ доляj·xj + v = hi·M. Всего 1 + n + 2k строк. Фаза 1 с искусственными переменными находит допустимую смесь или доказывает, что её нет: если сумма искусственных не дошла до нуля, ответ IMPOSSIBLE. Фаза 2 уменьшает цену.
4Разбор
Таблица плотная: не больше 81 строки и 221 столбца вместе с искусственными. Входящий столбец — с самой отрицательной приведённой стоимостью; после многих шагов подряд, которые не сдвигают точку, — первый подходящий по номеру (правило Бленда), чтобы не зациклиться. Выходящая строка — по наименьшему отношению, при равенстве — с меньшим номером базисной переменной. Все сравнения с допуском 10−9; ответ — Σ ценаj·xj в найденной вершине.
4+Решение
5Сложность
Шаг — O(m·n) ≈ 2·104 действий. Сколько шагов, заранее не сказать — гарантии многочленного числа шагов у симплекс-метода нет, — но на самом большом тесте решение на Python укладывается в четверть секунды.
6Типичные ошибки
- Забыть запасы. Это
wrong.py: без ограничения «не больше запаса» весь сплав набирается из самого выгодного сырья, и во втором примере вместоIMPOSSIBLEполучается цена. - Жадность. Брать сначала самое дешёвое сырьё, потом исправлять доли — не работает: дешёвый лом может испортить состав так, что исправлять придётся дорогим чистым металлом.
- Отрицательные правые части. Перед фазой 1 строки с отрицательной правой частью умножают на −1, иначе искусственные переменные стартуют с отрицательных значений.
- Целые килограммы. Задача разрешает дробные количества; требование целых сделало бы её задачей целочисленного программирования — её решают ветвями и границами поверх того же симплекс-метода.