Bedao Mini Contest 26 - Bán sách
Xem dạng PDF
Có ~N~ người dân sống ở ~1~ thành phố. Người thứ ~i~ sống ở vị trí ~x_i~ trên trục số và có sức ảnh hưởng là ~e_i~. Chủ tịch của thành phố đang muốn đẩy mạnh phong trào học tin nên họ muốn mọi người trong thành phố đều có sách tin học. Để làm điều này chủ tịch muốn tặng sách cho ~1~ số người trong thành phố và để những người này đi quảng bá sách cho họ. Cụ thể nếu người ~i~ có sách thì người ~j~ cũng sẽ đi mua sách nếu ~|x_i-x_j|\le e_i-e_j~. Hỏi chủ tịch cần phải tặng ít nhất bao nhiêu quyển sách để sau đó mọi người dân đều có sách.
Input
Dòng đầu tiên nhập vào số nguyên dương ~N~ ~(1\le N\le5\cdot10^5)~ chỉ số lượng người dân.
~N~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên ~x_i~ và ~e_i~ chỉ vị trí và sức ảnh hưởng của người dân thứ ~i~ ~(1\le x_i,e_i \le 10^9)~.
Output
In ra số lượng sách tối thiểu cần phải phát miễn phí cho người dân để sau đó mọi người đều có sách.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~10~ | ~e_1 = e_2 = · · · = e_N.~ |
| 2 | ~20~ | ~N ≤ 16.~ |
| 3 | ~30~ | ~N ≤ 1 000.~ |
| 4 | ~40~ | Không có điều kiện gì thêm. |
Sample Input 1
4
4 2
2 3
3 4
6 5
Sample Output 1
2
Sample Input 2
3
7 10
10 10
7 10
Sample Output 2
2
Notes
Giải thích test ví dụ ~1~:
Ví dụ, nếu Chủ tịch quyên tặng sách theo cách sau, tất cả cư dân trong Thành phố sẽ nhận được sách của Chủ tịch.
Chủ tịch tặng một bản sách cho Cư dân 3.
Vì ~|X_3 - X_1| = 1~ và ~E_3 - E_1 = 2~, Cư dân 1 sẽ mua một bản sách của Chủ tịch và nhận được nó.
Vì ~|X_3 - X_2| = 1~ và ~E_3 - E_2 = 1~, Cư dân 2 sẽ mua một bản sách của Chủ tịch và nhận được nó.
Vì ~|X_3 - X_4| = 3~ và ~E_3 - E_4 = -1~, Cư dân 4 sẽ không mua một bản sách của Chủ tịch.
Do đó, Cư dân 1, 2, 3 sẽ nhận được sách của Chủ tịch.
Chủ tịch tặng một bản sách cho Cư dân 4. Vì tất cả cư dân ngoại trừ Cư dân 4 đã nhận được sách của Chủ tịch, cuối cùng tất cả cư dân trong Thành phố đều nhận được sách của Chủ tịch.
Vì không thể quyên tặng sách cho ít hơn hai cư dân mà vẫn đảm bảo tất cả cư dân trong Thành phố nhận được sách của Chủ tịch, nên đầu ra là 2.
Bình luận
Xin hỏi, bài này có phải đọc từ tập tin hay không? Mình thấy trong bài không có tập tin nên không rõ. Đã test trên máy rất ok nhưng khi gửi không chạy được vì không biết tập tin là gì?
Bạn nhìn bên phải màn hình nằm trên mục Tác giả có phần Input , Output, khi nào yêu cầu rõ là từ file thì họ sẽ ghi tên file, còn stdin stdout là nhập xuất cơ bản không dùng file đó