Обмен входными карточками в метро
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Стек, очередь, связные списки
- Поиск и сортировка
- Математика
На линии метро stations станций с номерами от 1 до stations, поезд идёт от 1-й к последней. При входе пассажир получает карточку со своей станцией входа, при выходе сдаёт какую-то карточку и платит за расстояние d между станцией на карточке и станцией выхода: первая станция пути стоит N, вторая N − 1, i-я N + 1 − i (здесь N = stations), то есть всего d·N − d·(d − 1)/2; при d = 0 платить не нужно.
Дан список поездок journeys, каждая — тройка [o, e, p]: p пассажиров едут со станции o до станции e (o < e). Пассажиры могут сколько угодно раз меняться карточками с любыми попутчиками, которые находятся в поезде одновременно с ними, включая тех, кто выходит на станции их входа или входит на станции их выхода. Каждый выходит на своей станции и сдаёт ровно одну карточку. Город получил бы сумму honest без обменов и сумму paid при обменах, минимизирующих общую оплату. Верните потерю honest − paid по модулю 1000002013.
Ограничения: 2 ≤ stations ≤ 10^9, до 1000 поездок, 1 ≤ p ≤ 10^9; суммы огромны, считайте по модулю.
Пример: 6, [[1, 3, 1], [3, 6, 1]] → 6 (пассажиры меняются на станции 3).
Источник: Coding Competitions Archive, codejam/2013/round_2/ticket_swapping · © Google LLC · Apache-2.0 · условие переведено и дополнено