Выручка аттракциона
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Массивы и списки
- Математика
- Словари и множества
К американским горкам стоит очередь из групп людей: groups[i] — размер i-й группы. В вагончик помещается не больше capacity человек. Группы садятся по очереди с начала очереди, пока очередная группа помещается целиком и группы не закончились (группы нельзя разделять и обгонять); затем вагончик едет, даже если не полон. После поездки все пассажиры встают в конец очереди в том же порядке. Если в одной поездке уже посадили все группы, второй раз одну и ту же группу в эту поездку не сажают.
Горка совершит rides поездок. Каждый пассажир платит 1 за поездку. Верните общую выручку.
Ограничения: 1 ≤ rides ≤ 10^8, 1 ≤ capacity ≤ 5·10^7, 1 ≤ groups[i] ≤ min(capacity, 10^7), не больше 300 групп.
Пример: 4, 6, [1, 4, 2, 1] → 21 (поездки берут группы [1, 4], [2, 1, 1], [4, 2], [1, 1, 4]).
Источник: Coding Competitions Archive, codejam/2010/qualification_round/theme_park · © Google LLC · Apache-2.0 · условие переведено и дополнено