Фабрика коробок и игрушек
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Динамическое программирование
- Массивы и списки
На фабрике две конвейерные ленты: одна выпускает коробки, другая — игрушки, и у каждой коробки и игрушки есть тип. Вы берёте первую коробку и первую игрушку и на каждом шаге делаете одно из трёх: выбрасываете текущую коробку и берёте следующую, выбрасываете текущую игрушку и берёте следующую или, если типы совпадают, кладёте игрушку в коробку и отправляете покупателю (тогда берёте следующие коробку и игрушку). Порядок на лентах менять нельзя.
Ленты выпускают длинные серии одного типа. Список boxes состоит из пар [количество, тип]: сначала выходит boxes[0][0] коробок типа boxes[0][1], затем следующая серия и так далее; toys описывает игрушки так же. Верните наибольшее число игрушек, которые можно отправить в коробках. Серий на каждой ленте от 1 до 100, в одной серии от 1 до 2·10¹², типы от 1 до 100 — поэтому разворачивать серии в отдельные предметы нельзя.
Пример: [[10, 1], [20, 2], [25, 3]], [[10, 2], [30, 3], [20, 1]] → 35.
Источник: Coding Competitions Archive, codejam/2012/round_1c/box_factory · © Google LLC · Apache-2.0 · условие переведено и дополнено