Задача №115233. Восстание газонокосилок
Газоны в Иннополисе косят электрические роботы-газонокосилки. Будем считать, что газон представляет собой отрезок числовой прямой, на котором в некоторых точках расположены роботы-газонокосилки. Размером роботов можно пренебречь. Один из роботов стоит в начале газона (левее него газона нет), и один — в конце (правее него газона нет). Каждый робот изначально ориентирован в одном из двух направлений: либо направо, либо налево.
Заряда \(i\)-го робота хватает для обработки \(p_i\) метров газона. После ночной зарядки все роботы начинают работать одновременно и движутся с одинаковой скоростью. Каждый робот движется в своём направлении вдоль прямой. Робот останавливается в одном из трёх случаев:
- Если у робота закончился заряд. Иными словами, если \(i\)-й робот проехал \(p_i\) метров от точки старта.
- Если робот доехал до начала или конца газона.
- Если робот встретился в одной точке с другим роботом, который двигался ему навстречу или остановился в этой точке ранее.
Перед запуском роботов вы можете поменять направление некоторых из них на противоположное. Требуется скосить траву на всём газоне.
Определите, у какого минимального количества роботов нужно поменять направление, чтобы в итоге вся трава на газоне оказалась скошена. Иначе сообщите, что всю траву скосить невозможно.
В первой строке содержится целое число \(n\) (\(2 \leq n \leq 10^5\)) — количество роботов.
В следующих \(n\) строках содержатся описания роботов в порядке их расположения на прямой слева направо. Каждый робот характеризуется тремя целыми числами \(x_i\), \(p_i\), \(d_i\): начальной позицией робота, количеством метров, которые он может проехать, и направлением движения (\(0 = x_1 < x_2 < \ldots < x_n \le 10^9\), \(1 \le p_i \le 10^9\), значение \(d_i = -1\) обозначает движение налево, в направлении уменьшения координаты, \(d_i = 1\) обозначает движение направо, в направлении увеличения координаты). Начало и конец газона находятся в точках \(x_1=0\) и \(x_n\) соответственно.
В единственной строке необходимо вывести \(-1\), если скосить всю траву на газоне невозможно. Иначе, нужно вывести одно число — количество роботов, у которых нужно изменить направление на противоположное, чтобы газон был скошен.
| Ограничения | ||||
| Подз. | Баллы | \(n\) | дополнительно | Необх. подзадачи |
| 1 | 23 | \(n \le 10\) | У | |
| 2 | 16 | изначально все роботы ориентированы направо (\(d_i = 1\)) | ||
| 3 | 17 | \(n \le 1000\) | У, 1 | |
| 4 | 13 | \(x_i = i - 1\), \(p_i = 1\) | ||
| 5 | 14 | \(p_i = 10^9\) | ||
| 6 | 17 | без дополнительных ограничений | У, 1 – 5 | |
Первый пример изображен на рисунке. Для того, чтобы скосить всю траву, можно, например, развернуть робота, который стоит посередине.
3 0 1 -1 1 1 1 2 1 -1
1
2 0 1 1 4 2 -1
-1