JOI 2020 - Strawberry
Xem PDFTrang trại dâu tây Just Oishi Ichigo (gọi tắt là trang trại JOI) nổi tiếng vì có hình dạng dài và hẹp theo hướng đông-tây. Lối vào nằm ở đầu phía tây của trang trại. Ta gọi vị trí cách lối vào \(k\) mét về phía đông là vị trí \(k\).
Trong trang trại có \(N\) quả dâu tây, được đánh số từ \(1\) đến \(N\). Ban đầu các quả đều còn xanh. Quả dâu thứ \(i\) (\(1 \le i \le N\)) nằm ở vị trí \(A_i\) và chín đỏ vào thời điểm \(T_i\).
Không thể thu hoạch một quả khi nó còn xanh; tức là chỉ có thể thu hoạch quả thứ \(i\) từ thời điểm \(T_i\) trở đi. Bạn xuất phát từ lối vào ở vị trí \(0\) vào thời điểm \(0\), di chuyển theo hướng đông hoặc tây với tốc độ tối đa \(1\) mét mỗi giây để thu hoạch dâu. Có thể bỏ qua thời gian thu hoạch.
Cho thông tin về trang trại, hãy tìm thời gian ít nhất để thu hoạch tất cả các quả dâu khi chúng đã chín đỏ, rồi trở về lối vào.
Dữ liệu vào
Dữ liệu được cho từ đầu vào chuẩn theo dạng:
N
A_1 T_1
A_2 T_2
...
A_N T_N
Dữ liệu ra
In ra một dòng chứa thời gian ít nhất, tính bằng giây, để thu hoạch tất cả các quả dâu khi chúng đã chín đỏ rồi trở về lối vào.
Ràng buộc
- \(1 \le N \le 100\,000\).
- \(0 \le A_i \le 1\,000\,000\,000=10^9\) với \(1 \le i \le N\).
- \(0 \le T_i \le 1\,000\,000\,000=10^9\) với \(1 \le i \le N\).
- Tất cả các giá trị đầu vào đều là số nguyên.
Ví dụ
Ví dụ 1
Input
10
1 3
2 1
3 4
4 1
5 5
6 9
7 2
8 6
9 5
10 3Output
20Giải thích
Trong \(10\) giây đầu, đi đến vị trí \(10\); trên đường đi có thể lần lượt thu hoạch các quả \(2,4,5,7,8,9,10\). Sau đó, dành \(10\) giây quay về vị trí \(0\); trên đường về có thể lần lượt thu hoạch các quả \(6,3,1\). Như vậy, cả \(10\) quả đều được thu hoạch khi đã chín đỏ.
Ví dụ 2
Input
10
0 450
5 445
10 430
15 405
20 370
25 325
30 270
35 205
40 130
45 45Output
450Giải thích
Có thể di chuyển như sau để thu hoạch tất cả các quả khi đã chín đỏ trong \(450\) giây:
- Đi \(45\) giây đến vị trí \(45\). Lúc này là thời điểm \(45\), nên có thể thu hoạch quả \(10\). Sau đó đi \(45\) giây về vị trí \(0\).
- Tiếp theo, đi \(40\) giây đến vị trí \(40\). Lúc này là thời điểm \(130\), nên có thể thu hoạch quả \(9\). Sau đó đi \(40\) giây về vị trí \(0\).
- Tiếp theo, đi \(35\) giây đến vị trí \(35\). Lúc này là thời điểm \(205\), nên có thể thu hoạch quả \(8\). Sau đó đi \(35\) giây về vị trí \(0\).
- Tiếp theo, đi \(30\) giây đến vị trí \(30\). Lúc này là thời điểm \(270\), nên có thể thu hoạch quả \(7\). Sau đó đi \(30\) giây về vị trí \(0\).
- Tiếp theo, đi \(25\) giây đến vị trí \(25\). Lúc này là thời điểm \(325\), nên có thể thu hoạch quả \(6\). Sau đó đi \(25\) giây về vị trí \(0\).
- Tiếp theo, đi \(20\) giây đến vị trí \(20\). Lúc này là thời điểm \(370\), nên có thể thu hoạch quả \(5\). Sau đó đi \(20\) giây về vị trí \(0\).
- Tiếp theo, đi \(15\) giây đến vị trí \(15\). Lúc này là thời điểm \(405\), nên có thể thu hoạch quả \(4\). Sau đó đi \(15\) giây về vị trí \(0\).
- Tiếp theo, đi \(10\) giây đến vị trí \(10\). Lúc này là thời điểm \(430\), nên có thể thu hoạch quả \(3\). Sau đó đi \(10\) giây về vị trí \(0\).
- Tiếp theo, đi \(5\) giây đến vị trí \(5\). Lúc này là thời điểm \(445\), nên có thể thu hoạch quả \(2\). Sau đó đi \(5\) giây về vị trí \(0\).
- Bạn đến vị trí \(0\) đúng vào thời điểm \(450\), nên có thể thu hoạch quả \(1\). Bạn vừa thu hoạch xong tất cả các quả, vừa có mặt ở vị trí \(0\).
Ví dụ 3
Input
15
11 23
3 94
89 3
38 58
65 29
41 3
80 42
22 76
48 85
83 98
87 29
97 96
22 75
57 25
99 33Output
198Nguồn
Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.
Kỳ thi:
- JOI 2020 - Second Qualifier (8 Tháng 12., 2019)
Bình luận