| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 10 | 5 | 5 | 50.000% |
Газоны в Иннополисе косят электрические роботы-газонокосилки. Будем считать, что газон представляет собой отрезок числовой прямой, на котором в некоторых точках расположены роботы-газонокосилки. Размером роботов можно пренебречь. Один из роботов стоит в начале газона (левее него газона нет), и один --- в конце (правее него газона нет). Каждый робот изначально ориентирован в одном из двух направлений: либо направо, либо налево.
Заряда $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,ドル если скосить всю траву на газоне невозможно. Иначе, нужно вывести одно число --- количество роботов, у которых нужно изменить направление на противоположное, чтобы газон был скошен.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 23 | $n \le 10$ |
| 2 | 16 | изначально все роботы ориентированы направо ($d_i = 1$) |
| 3 | 17 | $n \le 1000$ |
| 4 | 13 | $x_i = i - 1,ドル $p_i = 1$ |
| 5 | 14 | $p_i = 10^9$ |
| 6 | 17 | без дополнительных ограничений |
3 0 1 -1 1 1 1 2 1 -1
1
2 0 1 1 4 2 -1
-1
Первый пример изображен на рисунке. Для того, чтобы скосить всю траву, можно, например, развернуть робота, который стоит посередине.