ĐOÀN XE QUA CẦU

Xem PDF

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Trên tuyến đường một chiều, tình trạng giao thông trở nên đông đúc. Để đảm bảo an toàn, lực lượng chức năng phân nhóm cho các xe qua cầu. Các xe phải di chuyển tuần tự theo nhóm (nghĩa là nhóm \( i \) chỉ được di chuyển sau khi toàn bộ xe của nhóm \( i - 1 \) đã qua cầu và các xe không được phép vượt nhau), tổng trọng lượng của các xe trong cùng một nhóm không được vượt quá trọng tải của cầu. Thời gian qua cầu của mỗi nhóm bằng thời gian qua cầu của xe có vận tốc thấp nhất trong nhóm.
\( n \) xe đến cầu, các xe được đánh số thứ tự từ 1 đến \( n \), xe thứ \( i \) có vận tốc là \( w_i \) và chạy với vận tốc là \( v_i \). Biết cầu có trọng tải \( P \), chiều dài \( L \). Giả thiết rằng \( P \geq w_i \) với \( 1 \leq i \leq n \).

Yêu cầu:

Bỏ qua khoảng cách giữa các xe, hãy tìm phương án tách đoàn xe thành từng nhóm để toàn bộ xe qua cầu được đảm bảo an toàn và tổng thời gian qua cầu là nhỏ nhất.

Dữ liệu:

Có dạng:

  • Dòng đầu ghi ba số nguyên \( n, P, L \) (\( 1 \leq n \leq 1000, 1 \leq P \leq 100, 1 \leq L \leq 1000 \)).
  • Dòng thứ \( i \) trong \( n \) dòng tiếp theo ghi hai số nguyên là \( w_i, v_i \) (\( 1 < w_i \leq P, 1 \leq v_i \leq 100 \)).

Kết quả:

Gồm một dòng duy nhất chứa một số thực là thời gian nhỏ nhất tìm được (làm tròn 2 chữ số thập phân).

INPUT

10 100 100
40 25
50 20
50 20
70 10
12 50
9 70
49 30
38 35
27 50
19 70

OUTPUT

24.33

Giải thích:

  • Nhóm 1: Xe 1 – thời gian qua cầu: 4.00
  • Nhóm 2: Xe 2, 3 – thời gian qua cầu: 5.00
  • Nhóm 3: Xe 4, 5, 6 – thời gian qua cầu: 10.00
  • Nhóm 4: Xe 7, 8 – thời gian qua cầu: 3.33
  • Nhóm 5: Xe 9, 10 – thời gian qua cầu: 2.00

Tổng thời gian qua cầu:
\( 4.00 + 5.00 + 10.00 + 3.33 + 2.00 = 24.33 \)


Bình luận

  • wibulordsama 8:16 p.m. 7 Tháng 3, 2025 đã chỉnh sửa

    Sao mình ghi đúng tên file nhập xuất mà nó báo không thấy file xuất ra là như nào v
    PS: vc đề , trên thì nhập bàn phím, dưới bảo nhập xuất file, chịu