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 (), độ rộng của mỗi làn (), tốc độ của các tàu và tốc độ của phà (), thời điểm xuất phát sớm nhất và thời điểm xuất phát muộn nhất của phà (). 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 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 , số tàu trong làn ( với mọi ). Sau đó là cặp số nguyên và ( và ). Chiều dài của tàu thứ trong làn là , còn là vị trí tại thời điểm 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à và nhiều nhất là .
Dữ liệu ra
In ra giá trị lớn nhất sao cho tồn tại thời điểm mà phà có thể bắt đầu băng qua an toàn tại mọi thời điểm với . Ngoài ra, phà không được bắt đầu băng qua trước thời điểm và phải bắt đầu không muộn hơn thời điểm .
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á . Bạn có thể giả sử tồn tại một khoảng thời gian với giây để phà băng qua.
Ràng buộc
- , , , .
- , tổng số tàu từ đến .
- , ; 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 .
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 giây. Các thời điểm xuất phát bị cấm trong là (tàu dài ở làn 2), và (làn 1), và (làn 2), (làn 3). Khoảng trống dài nhất là từ đến . |
| 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 , , , ; phà ở trong làn giây nên các thời điểm xuất phát bị cấm là , , , . Khoảng trống dài nhất là từ đến . |
Bình luận