trang chủ / đề bài / icpcwf19_k

Đèn đỏ phiền toái

Đề bài

Mô tả

Xe hơi! Chúng từ đâu đến? Chúng đi về đâu? Không ai biết. Chúng xuất hiện ở bất cứ nơi nào có đường, như thể từ hư không. Có người nói không có hai chiếc xe nào giống hệt nhau. Có người nói nếu nhìn kỹ, bạn sẽ thấy bóng ma nhợt nhạt của những con người khốn khổ bị giam mãi bên trong, nhất là vào buổi sáng và lúc chiều muộn. Con mắt khoa học nào có thể nắm bắt được sự đối xứng đáng sợ của chúng?

Hy vọng là con mắt của bạn. Là thành viên Ban Điều khiển Giao thông Đô thị của chính quyền, bạn đang viết một bài báo về tình trạng ùn tắc giao thông ở địa phương. Tất nhiên, quan sát xe hơi ngoài tự nhiên thì quá nguy hiểm, nhưng bạn được cung cấp dữ liệu về các đèn giao thông dọc Phố Chính của thị trấn, và bạn muốn làm vài tính toán lý thuyết xem các đèn này được đồng bộ tốt đến mức nào.

Phố Chính là một đường thẳng, trên đó đặt các đèn giao thông tại nhiều điểm khác nhau. Mỗi đèn luân phiên giữa đỏ và xanh với chu kỳ cố định: đỏ trong r giây, rồi xanh trong g giây, rồi lại đỏ trong r giây, và cứ thế. Giá trị r và g có thể khác nhau ở các đèn khác nhau. Tại thời điểm 0, mọi đèn đều vừa chuyển sang đỏ.

Giả sử một chiếc xe "lý tưởng" xuất hiện một cách thần bí ở đầu phía tây của Phố Chính tại một thời điểm thực ngẫu nhiên phân bố đều trong đoạn [0,2019!] (với k! là tích của k số nguyên dương đầu tiên), rồi chạy về phía đông với tốc độ chậm rì 1 mét/giây cho đến khi gặp đèn đỏ. Xác suất để xe đi qua tất cả các đèn mà không phải dừng là bao nhiêu? Nếu xe gặp đèn đỏ, thì khả năng đèn đỏ đầu tiên nó gặp là đèn nào?

Hãy viết chương trình trả lời các câu hỏi này.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n, số đèn giao thông. Mỗi dòng trong n dòng tiếp theo chứa ba số nguyên x, r và g mô tả một đèn: x là vị trí của đèn trên Phố Chính (tính bằng mét), r và g là thời lượng (tính bằng giây) của phần đỏ và phần xanh trong chu kỳ của đèn (tức là đèn đỏ từ thời điểm 0 đến r, từ r+g đến 2r+g, và cứ thế).

Đầu phía tây của Phố Chính ở vị trí 0, các đèn được liệt kê theo thứ tự vị trí tăng chặt.

Dữ liệu ra

Với mỗi đèn trong n đèn (theo thứ tự của input), in ra trên một dòng xác suất để đèn này là đèn đỏ đầu tiên mà chiếc xe "lý tưởng" gặp. Sau đó in thêm một dòng chứa xác suất để chiếc xe đi hết đường mà không phải dừng lần nào. Mỗi số được chấp nhận nếu sai số tuyệt đối không quá 10−6.

Ràng buộc

  • 1≤n≤500.
  • 1≤x≤105, các giá trị x tăng chặt.
  • 0≤r, 0≤g và 1≤r+g≤100.

Ví dụ

Input Output Giải thích
4
1 2 3
6 2 3
10 2 3
16 3 4
0.4
0
0.2
0.171428571429
0.228571428571
Ba đèn đầu có cùng chu kỳ 5. Xe đến đèn 1 ở thời điểm t+1 và bị dừng khi (t+1)mod5<2, xác suất 25. Xe qua được đèn 1 thì cũng qua được đèn 2, vì (t+6)mod5=(t+1)mod5.
6
4 1 5
9 8 7
13 3 5
21 5 7
30 9 1
2019 20 0
0.166666666667
0.466666666667
0.150000000000
0.108333333333
0.091666666667
0.016666666667
0.000000000000
Đèn cuối có g=0, luôn đỏ, nên xe chắc chắn phải dừng ở đâu đó.

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