Рулон кабеля
Склад продаёт кабель кусками стандартных длин: кусок длиной li метров стоит ci тенге, и покупателей на каждый вид кусков сколько угодно. На складе один рулон длиной L метров. Его режут на стандартные куски любых видов в любом количестве, а остаток, если он меньше любого куска или резать его невыгодно, выбрасывают. Сколько тенге можно выручить за рулон?
Рулоны бывают очень длинными — до триллиона метров: это не один барабан, а годовой выпуск завода, который удобно считать одним рулоном.
Вход
В первой строке n и L (1 ≤ n ≤ 100, 1 ≤ L ≤ 1012). Дальше n строк: длина куска li в метрах и его цена ci в тенге (1 ≤ li ≤ 100, 0 ≤ ci ≤ 2·106).
Выход
Наибольшая выручка в тенге.
Примеры
Пример 1
2 10 3 5000 5 8000
16000
Пример 2
2 7 2 1000 9 99000
3000
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если бы рулон был коротким, хватило бы неограниченного рюкзака: g[x] — лучшая выручка с x метров. Но таблица на 1012 клеток не поместится. Какой кусок будет занимать почти весь длинный рулон?
2Подсказка 2
Пусть b — кусок с наибольшей ценой за метр. Режем как можно больше кусков b, а остаток — лучшим образом. Проверьте это на первом примере: рулон 10 м, куски 3 м за 5000 и 5 м за 8000.
3Подсказка 3
Возьмите в каком-нибудь лучшем раскрое lb кусков, отличных от b, и посмотрите на суммы длин первых из них — 0, первый, первые два, … — по модулю lb. Что можно сделать с группой кусков, чья общая длина делится на lb?
4Идея
Среди лучших раскроев есть такой, где кусков, отличных от b, меньше lb. Значит, они занимают меньше lb · 100 ≤ 104 метров, а всё остальное — куски b. Посчитаем неограниченный рюкзак g[x] только до D = min(L, lb · max li) и переберём, сколько метров x ≤ D отдать «прочим» кускам: ответ — максимум g[x] + ⌊(L − x) / lb⌋ · cb.
5Разбор
Почему прочих кусков можно оставить меньше lb. Пусть их хотя бы lb; выпишем любые lb из них подряд и посчитаем lb + 1 сумм длин их начал, от пустой до полной. Остатков по модулю lb всего lb, значит, две суммы дают одинаковый остаток, и куски между ними вместе имеют длину m · lb. Заменим эту группу на m кусков b: длина та же, а выручка не уменьшится, ведь у каждого куска группы цена за метр не выше, чем у b. Прочих кусков стало меньше; повторяем, пока их не станет меньше lb.
Каждый кандидат g[x] + ⌊(L − x) / lb⌋ · cb — честный раскрой, так что ответ не больше лучшего. И не меньше: для лучшего раскроя из доказательства прочие куски занимают какие-то x ≤ D метров, g[x] не меньше их выручки, а кусков b в оставшиеся L − x метров влезает не меньше, чем в этом раскрое.
Лучший кусок выбираем сравнением c1 · l2 > c2 · l1 в целых числах, без деления. Выручка доходит до 2·1018 — это ещё помещается в int64.
Жадная идея из второй подсказки ошибается на первом же примере: три куска по 3 м дают 15 000 и метр в отходы, а два куска по 5 м — 16 000. Иногда выгодно отрезать на один-два лучших куска меньше, чтобы остаток лёг без потерь.
5+Решение
6Сложность
O(n · D), где D ≤ 104: около миллиона шагов, сколько бы ни был длинен рулон.
7Типичные ошибки
- Таблица на весь рулон. Триллион клеток не поместится ни в какую память.
- Сначала все лучшие куски, потом остаток. Не проходит первый пример — см. разбор.
- Лучший кусок по цене за метр в числах с плавающей точкой. При почти равных ценах за метр деление может перепутать порядок; сравнивайте произведения.