Đi Trên Đồi
Đề bài
Mô tả
Có đoạn dốc, mỗi đoạn là một đoạn thẳng từ điểm đến với và (dốc đi lên từ trái sang phải). Không có hai đoạn dốc nào chạm nhau, kể cả tại đầu mút.
Bạn bắt đầu tại , điểm này được đảm bảo là đầu trái của đúng một đoạn dốc (đoạn đó không nhất thiết được cho đầu tiên trong dữ liệu vào). Bạn đi theo hướng tăng . Khi đến đầu phải của đoạn dốc đang đứng, bạn rơi thẳng xuống theo phương thẳng đứng. Nếu có đoạn dốc khác chứa hoành độ theo nghĩa (đầu trái đóng, đầu phải mở) và có độ cao tại nhỏ hơn , bạn rơi xuống đoạn dốc cao nhất trong số đó rồi tiếp tục đi. Nếu không có đoạn nào như vậy, bạn rơi mãi mãi.
Đếm tổng số đoạn dốc bạn đã đi trên đó trong suốt hành trình.
Dữ liệu vào
- Dòng 1: Số nguyên
- dòng tiếp theo: Bốn số nguyên mô tả mỗi đoạn dốc
Dữ liệu ra
Số nguyên: tổng số đoạn dốc đã đi trên đó.
Ràng buộc
- và với mọi đoạn dốc
- Không có hai đoạn dốc nào chạm nhau, kể cả tại đầu mút
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 0 0 5 6 1 0 2 1 7 2 8 5 3 0 7 7 |
3 | Đi trên đoạn 1 (0,0)→(5,6), rơi xuống đoạn 4 (3,0)→(7,7) vì tại đoạn này cao , thấp hơn . Đi tiếp tới (7,7), rơi xuống đoạn 3 (7,2)→(8,5), rồi rơi mãi mãi. |
| 4 1 0 2 1 7 2 8 5 3 0 7 7 0 0 5 6 |
3 | Cùng bốn đoạn dốc nhưng thứ tự khác. Điểm xuất phát nằm trên đoạn số 4, không phải đoạn số 1. |
Bình luận