Повалити якнайбільше дерев (за кількістю)

Перегляд у форматі PDF

Надіслати розв'язок

Бали: 1,00 (partial)
Time limit: 0.5s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type

Є ~n~ дерев, розміщених уздовж дороги в точках з координатами ~x_1~, ~x_2~, ..., ~x_n~. Кожне дерево має свою висоту ~h_i~. Дерево можна зрубати і повалити або ліворуч, або праворуч. Тоді воно буде займати або відрізок ~[x_i - h_i, x_i]~, або ~[x_i; x_i + h_i]~ відповідно. Поки дерево не зрубане, воно займає точку з координою ~x_i~. Дерево можна повалити, якщо на відрізку, який воно має займати після звалювання, немає жодної зайнятої точки.

Яку найбільшу кількість дерев можна повалити?

Вхідні дані

У першому рядку задане ціле число ~n~ (~1\leqslant n\leqslant 10^5~) – кількість дерев. У наступних ~n~ рядках задані пари цілих чисел ~x_i\,\,h_i~ (~1\leqslant x_i\leqslant 10^9~, ~1\leqslant h_i\leqslant 10^9~) – координата і висота ~i~-го дерева. Пари задані у порядку зростання ~x_i~. Жодні два дерева не знаходяться в точці з однаковою координатою.

Результати

Потрібно вивести одне число – максимальну кількість дерев, які можна зрубати й повалити згідно зазначених правил.

Приклади

Вхід

4
10 4
15 1
19 3
20 1

Результат

4

Вхід

5
1 2
2 1
5 10
10 9
19 1

Результат

3

Коментарі

Please read the guidelines before commenting.


Ще немає коментарів.