Đề thi Olympic khối DTNT cấp Tỉnh lần 2 môn Tin học Lớp 11 - Sở GD&ĐT Đăk Nông - Năm học 2015-2016 - Đề dự bị (Có đáp án)

Câu 2 (7,0 điểm). (Đặt tên là Duyet.pas)

Xét lưới ô vuông tạo thành từ n*n đường, các đường của lưới được đánh số từ 1 đến n từ trái qua phải và từ trên xuống dưới (1≤n≤20000). Ở mỗi hàng thứ i, người ta cho đoạn thẳng xác định bởi hai điểm li và ri (1≤li≤ri≤n, i=1…n).

Yêu cầu: Xác định độ dài của đường đi ngắn nhất dọc theo các cạnh của lưới từ điểm (1,1) đến điểm (n,n) và thoả mãn các điều kiện:

• Chỉ đi sang phải, sang trái hoặc xuống dưới
• Đi qua tất cả các điểm thuộc các đoạn thẳng đã cho

Dữ liệu: Vào từ file văn bản DUYET.INP:

• Dòng đầu tiên chứa số nguyên dương n
• Dòng thứ i trong n dòng sau chứa hai số nguyên dương li, ri

Kết quả: Đưa ra file văn bản DUYET.OUT một số nguyên duy nhất là độ dài của đường đi ngắn nhất tìm được.

Ví dụ: