trang chủ / đề bài / icpcwf15_i

Giao thông trên eo biển

Đề bài

Mô tả

Các phà đi qua eo biển Gibraltar từ Maroc sang Tây Ban Nha phải điều khiển cẩn thận để tránh dòng tàu thuyền dày đặc chạy dọc eo biển. Hãy viết chương trình giúp thuyền trưởng phà tìm khoảng trống lớn nhất trong dòng tàu để băng qua an toàn.

Chương trình của bạn dùng một mô hình đơn giản như sau. Eo biển có một số làn hàng hải song song theo hướng đông tây. Các tàu chạy với cùng một tốc độ không đổi, hoặc về phía đông, hoặc về phía tây. Mọi tàu trong cùng một làn chạy cùng một hướng. Dữ liệu vệ tinh cho biết vị trí của các tàu trong từng làn. Các tàu có thể có chiều dài khác nhau. Các tàu không đổi làn và không đổi tốc độ vì chiếc phà băng qua.

Phà chờ một thời điểm thích hợp khi có một khoảng trống đủ lớn trong dòng tàu. Sau đó phà băng qua eo biển theo hướng bắc, dọc theo một đường thẳng bắc nam, với tốc độ không đổi. Từ thời điểm phà đi vào một làn cho đến thời điểm phà rời khỏi làn đó, không tàu nào trong làn đó được chạm vào đường băng qua. Phà nhỏ đến mức có thể bỏ qua kích thước của nó.

Hình dưới minh họa các làn và các tàu của ví dụ 1 (phà xuất phát ở chấm đen phía dưới, đi lên theo đường nét đứt; phía trên là hướng bắc, bên phải là hướng đông).

Nhiệm vụ của bạn là tìm khoảng thời gian dài nhất mà trong đó phà có thể băng qua eo biển an toàn.

Dữ liệu vào

Dòng đầu tiên gồm sáu số nguyên: số làn n (1≤n≤105), độ rộng w của mỗi làn (1≤w≤1000), tốc độ u của các tàu và tốc độ v của phà (1≤u,v≤100), thời điểm xuất phát sớm nhất t1 và thời điểm xuất phát muộn nhất t2 của phà (0≤t1<t2≤106). Mọi độ dài tính bằng mét, mọi tốc độ tính bằng mét/giây, mọi thời gian tính bằng giây.

Mỗi dòng trong n dòng tiếp theo chứa dữ liệu của một làn. Mỗi dòng bắt đầu bằng ký tự E hoặc W: E nghĩa là các tàu trong làn này chạy về phía đông, W nghĩa là các tàu trong làn này chạy về phía tây. Tiếp theo là số nguyên mi, số tàu trong làn (0≤mi≤105 với mọi 1≤i≤n). Sau đó là mi cặp số nguyên lij và pij (1≤lij≤1000 và −106≤pij≤106). Chiều dài của tàu thứ j trong làn i là lij, còn pij là vị trí tại thời điểm 0 của đầu mũi tàu, tức là đầu phía trước theo hướng tàu chạy.

Vị trí của các tàu trong mỗi làn được tính tương đối so với đường băng qua của phà. Vị trí âm nằm ở phía tây đường băng qua, vị trí dương nằm ở phía đông. Các tàu không chồng lên nhau và không chạm nhau, và được liệt kê theo thứ tự vị trí tăng dần. Các làn được liệt kê theo khoảng cách tăng dần tính từ điểm xuất phát của phà, điểm này nằm ngay phía nam làn đầu tiên. Giữa các làn không có khoảng trống. Tổng số tàu ít nhất là 1 và nhiều nhất là 105.

Dữ liệu ra

In ra giá trị lớn nhất d sao cho tồn tại thời điểm s mà phà có thể bắt đầu băng qua an toàn tại mọi thời điểm t với s≤t≤s+d. Ngoài ra, phà không được bắt đầu băng qua trước thời điểm t1 và phải bắt đầu không muộn hơn thời điểm t2.

Kết quả được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá 10−3. Bạn có thể giả sử tồn tại một khoảng thời gian với d>0,1 giây để phà băng qua.

Ràng buộc

  • 1≤n≤105, 1≤w≤1000, 1≤u,v≤100, 0≤t1<t2≤106.
  • 0≤mi≤105, tổng số tàu từ 1 đến 105.
  • 1≤lij≤1000, −106≤pij≤106; trong mỗi làn các tàu không chồng lên nhau, không chạm nhau và được liệt kê theo vị trí tăng dần.
  • Tồn tại đáp án d>0,1.

Ví dụ

Input Output Giải thích
3 100 5 10 0 100
E 2 100 -300 50 -100
W 3 10 60 50 200 200 400
E 1 100 -300
6.00000000 Phà đi hết một làn trong 100/10=10 giây. Các thời điểm xuất phát bị cấm trong [0,100] là [−8,4] (tàu dài 10 ở làn 2), [10,30] và [50,80] (làn 1), [20,40] và [60,110] (làn 2), [30,60] (làn 3). Khoảng trống dài nhất là từ 4 đến 10.
1 100 5 10 0 200
W 4 100 100 100 300 100 700 100 900
50.00000000 Các tàu chạm đường băng qua trong các khoảng [20,40], [60,80], [140,160], [180,200]; phà ở trong làn 10 giây nên các thời điểm xuất phát bị cấm là [10,40], [50,80], [130,160], [170,200]. Khoảng trống dài nhất là từ 80 đến 130.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0