Đề 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ụ:

doc 2 trang Hữu Vượng 29/03/2023 4680
Bạn đang xem tài liệu "Đề 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)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • docde_thi_olympic_khoi_dtnt_cap_tinh_lan_2_mon_tin_hoc_lop_11_s.doc