Submit | All submissions | Best solutions | Back to list |
PROCHAT - Chặt |
Hồi nhỏ Susie là một cô nàng rất thông, nên bây giờ Susie rất giàu có. Cô muốn xây một ngồi nhà thật to làm bằng gỗ đẹp và quý. Thật may mắn bên đường có hàng cây thỏa mãn yêu cầu của cô.
Có n cây nằm dọc đường tại các điểm có tọa độ x 1 , x 2 , ..., x n . Mỗi cây có chiều cao h i . Susie có thể chặt một cây rồi hạ họ sang bên trái hoặc bên phải. Khi đó nó chiếm một trong những phân đoạn [ x i - h i , x i ] hoặc [ x i ; x i + h i ] . Cây mà không được chặt thì chỉ chiếm một điểm duy nhất tại tọa độ x i . Susie chỉ có thể hạ một cây nếu phân đoạn của nó không chứa bất kỳ điểm bị chiếm đóng khác.
Cô ấy muốn hạ được số lượng cây nhiều nhất, nhưng cô ấy không giỏi toán nên bạn hãy tính giúp cô ấy nhé
Input
Dòng đầu tiên chứa số nguyên n ( 1 ≤ n ≤ 10 5 ) - số cây.
Tiếp theo n dòng chứa các cặp số nguyên x i , h i ( 1 ≤ x i , h i ≤ 10 9 ) - tọa độ và chiều cao của cây thứ i.
Các cặp được đưa ra trong thứ tự tăng dần x i . Không có hai cây nằm cùng một tọa độ điểm.
Output
In một số duy nhất - số lượng cây tối đa mà bạn có thể hạ chúng thỏa mãn yêu cầu đề bài.
Example
Input1: 5
1 2
2 1
5 10
10 9
19 1 Output1: 3
Input2: 5
1 2
2 1
5 10
10 9
20 1 Output2: 4
Chú thích:
Trong các mẫu đầu tiên, bạn có hạ những cây như sau :
- Hạ cây 1 - sang bên trái - bây giờ nó chiếm phân khúc [- 1; 1]
- Hạ cây 2 - sang bên phải - bây giờ nó chiếm phân khúc [2, 3]
- Cây 3 không hạ được - nó chiếm điểm 5
- Cây 4 không hạ được - nó chiếm điểm 10
- Hạ cây 5 - sang bên phải - bây giờ nó chiếm phân khúc [19; 20].
Added by: | Frost |
Date: | 2016-03-12 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | MAWK BC C NCSHARP CPP CPP14 COFFEE DART FORTH JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA |
Resource: | Frost |