trang chủ / đề bài / icpcwf18_a

Bắt kịp chuyến bay

Đề bài

Mô tả

Chuyến bay của bạn tới vòng chung kết ICPC sắp cất cánh, và cách duy nhất để tới sân bay là đi xe buýt. Không may là một số tài xế xe buýt đang tính chuyện đình công, nên bạn không biết liệu mình có tới sân bay kịp giờ hay không. Mục tiêu của bạn là lên kế hoạch cho hành trình sao cho xác suất kịp chuyến bay là lớn nhất.

Bạn có bản đồ chi tiết của thành phố, gồm mọi bến xe buýt. Bạn đang ở bến 0 và sân bay là bến 1. Bạn cũng có lịch trình đầy đủ: mỗi chuyến xe rời bến xuất phát lúc nào và tới bến đích lúc nào. Ngoài ra, với mỗi chuyến xe bạn biết xác suất nó thực sự chạy đúng lịch, thay vì tài xế đình công và chuyến xe bị hủy. Giả sử mọi sự kiện này độc lập với nhau: xác suất một chuyến xe chạy đúng lịch không thay đổi khi bạn biết các chuyến khác có chạy hay không.

Nếu bạn tới một bến trước giờ khởi hành của một chuyến xe thì bạn có thể chuyển sang chuyến xe đó. Nhưng nếu bạn tới đúng vào giờ khởi hành thì bạn không kịp lên xe. Bạn không thể kiểm tra trước một chuyến xe có chạy hay không: bạn chỉ biết điều đó khi thử lên xe. Vì vậy, nếu có hai chuyến xe trở lên rời cùng một bến vào cùng một thời điểm, bạn chỉ có thể thử lên một trong số chúng.

Xét lịch trình dưới đây (ứng với ví dụ thứ nhất). Mỗi dòng là một chuyến xe với bến xuất phát, bến đích, giờ khởi hành và giờ tới nơi; bên cạnh một số chuyến có ghi xác suất chuyến đó chạy. Các chuyến không ghi xác suất chắc chắn chạy (100%).

Chuyến Bến xuất phát Bến đích Giờ khởi hành Giờ tới nơi Xác suất chạy
1 0 1 0 900 20%
2 0 2 100 500
3 2 1 500 700
4 2 1 501 701 10%
5 0 3 200 400 50%
6 3 1 500 800 10%
7 3 0 550 650 90%
8 0 1 700 900 10%

Bạn có thể thử bắt chuyến thứ nhất. Nếu nó chạy, nó đưa bạn thẳng tới sân bay và bạn không còn gì phải lo. Nếu nó không chạy, mọi chuyện phức tạp hơn. Bạn có thể lên chuyến thứ hai tới bến 2. Chuyến này chắc chắn chạy, nhưng bạn sẽ tới quá muộn để bắt chuyến thứ ba, chuyến lẽ ra đưa bạn tới sân bay kịp giờ. Chuyến thứ tư thì bạn bắt kịp, nhưng nó chỉ chạy với xác suất 0,1. Đó là một canh bạc tồi, nên tốt hơn là ở lại bến 0 và chờ chuyến thứ năm. Nếu bắt được chuyến này, bạn có thể thử lên chuyến thứ sáu tới sân bay; nếu chuyến đó không chạy, bạn vẫn còn cơ hội quay về bến 0 và bắt chuyến cuối cùng đi thẳng tới sân bay.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên m và n: số chuyến xe buýt và số bến trong thành phố. Dòng tiếp theo chứa một số nguyên k: thời điểm muộn nhất bạn phải có mặt ở sân bay.

Mỗi dòng trong m dòng tiếp theo mô tả một chuyến xe, gồm các số nguyên a và b (bến xuất phát và bến đích), tiếp theo là các số nguyên s và t (giờ rời bến a và giờ tới bến b). Giá trị cuối cùng trên dòng là số thực p: xác suất chuyến xe chạy đúng lịch.

Dữ liệu ra

In ra xác suất bạn kịp chuyến bay nếu hành động tối ưu. Đáp án được chấp nhận nếu sai số tuyệt đối không quá 10−6.

Ràng buộc

  • 1≤m≤106, 2≤n≤106.
  • 1≤k≤1018.
  • 0≤a,b<n, a≠b.
  • 0≤s<t≤k.
  • 0≤p≤1, có không quá 10 chữ số sau dấu thập phân.

Ví dụ

Input Output Giải thích
8 4
1000
0 1 0 900 0.2
0 2 100 500 1.0
2 1 500 700 1.0
2 1 501 701 0.1
0 3 200 400 0.5
3 1 500 800 0.1
3 0 550 650 0.9
0 1 700 900 0.1
0.3124 Lịch trình trong bảng ở trên. Thử chuyến 1; nếu hủy thì thử chuyến 5 tới bến 3 (nếu chuyến 5 cũng hủy thì chờ chuyến 8), ở bến 3 thử chuyến 6, nếu hủy thì về bến 0 bằng chuyến 7 và thử chuyến 8: 0,2+0,8·(0,5·(0,1+0,9·0,9·0,1)+0,5·0,1)=0,3124.
4 2
2
0 1 0 1 0.5
0 1 0 1 0.5
0 1 1 2 0.4
0 1 1 2 0.2
0.7 Lúc 0 chỉ thử được một trong hai chuyến đầu (0,5), lúc 1 thử chuyến có xác suất 0,4: 0,5+0,5·0,4=0,7.

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