TLEOJ Contest #16 - Cuộc phiêu lưu trên đồ thị Descartes

View as PDF

Submit solution

Points: 100
Time limit: 0.5s
Python 3 1.3s
Memory limit: 16M
Python 3 36M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C++, pypy3, Python

Đồ thị Descartes là một khái niệm không xa lạ với mọi người. Chắc hẳn trong những năm tháng THCS, khi là những cô bé, cậu bé mới lớn, chúng ta đã làm việc rất nhiều với đồ thị này.

Đồ thị Descartes được đặt theo tên của nhà toán học và triết học người Pháp René Descartes (1596-1650). Ông được biết đến với câu nói nổi tiếng "Cogito, ergo sum" (Tôi tư duy, vậy tôi tồn tại). Descartes không chỉ đóng góp cho triết học mà còn có những phát minh quan trọng trong lĩnh vực toán học. Hệ tọa độ Descartes, nền tảng của đồ thị này, được ông phát triển, giúp kết nối giữa hình học và đại số.

Hôm nay bạn X quyết định thực hiện một cuộc phiêu lưu trên đồ thị này!

Cho n điểm trên mặt phẳng.
X muốn tìm đường đi dài nhất thoả mãn điều kiện sau để thực hiện cuộc phiêu lưu:

Đầu tiên xuất phát tại 1 điểm bất kì
Trong 1 bước nếu đang đứng tại ô (x, y) có thể đi sang (a, b) nếu x \leq ay \leq b

Hãy tìm độ dài đó nhé!

Input and Output

Input
  • Dòng đầu gồm số nguyên n (n \leq 10^5)
  • n dòng sau, mỗi dòng chứa 2 số nguyên dương x_i, y_i (1 \leq x_i, y_i \leq 10^9) cách nhau một dấu cách.
Output
  • Một dòng duy nhất chứa số nguyên là đáp án của bài toán

Test 1

Input
4 
1 2
2 5
3 3
4 4
Output
3
Note

Từ điểm (1, 2) \rightarrow (3, 3) \rightarrow (4, 4).


Comments

There are no comments at the moment.