Набеги на Великую стену
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Массивы и списки
- Поиск и сортировка
Стена тянется вдоль всей числовой прямой и вначале везде имеет высоту 0. Кочевые племена атакуют её: атака бьёт по отрезку [w, e] (w < e, все вещественные точки между ними) с силой s. Атака отбита, если высота стены не меньше s во всех точках отрезка, иначе она успешна. После атаки каждая точка отрезка ниже s поднимается до s. Если в один день атак несколько, все они проверяются по стене начала дня, а стена поднимается только после них.
Элемент tribes[i] — восемь чисел [d, n, w, e, s, dd, dp, ds]: первая атака племени в день d по отрезку [w, e] с силой s, всего n атак, и каждая следующая происходит через dd дней (dd ≥ 1), сдвинута на dp (отрицательное — на запад) и сильнее на ds (может быть отрицательным; сила всех атак не меньше 1). Верните число успешных атак. Племён до 1000, атак у племени до 1000, координаты по модулю до 10⁸.
Пример: [[0, 3, 0, 2, 10, 2, 3, -2], [10, 3, 2, 3, 8, 7, 2, 0]] → 5 (атака в день 10 по [2, 3] прорывается, например, в точке 2,5).
Источник: Coding Competitions Archive, codejam/2013/round_1c/the_great_wall · © Google LLC · Apache-2.0 · условие переведено и дополнено