Đè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 giây, rồi xanh trong giây, rồi lại đỏ trong giây, và cứ thế. Giá trị và có thể khác nhau ở các đèn khác nhau. Tại thời điểm , 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 (với là tích của số nguyên dương đầu tiên), rồi chạy về phía đông với tốc độ chậm rì 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 , số đèn giao thông. Mỗi dòng trong dòng tiếp theo chứa ba số nguyên , và mô tả một đèn: là vị trí của đèn trên Phố Chính (tính bằng mét), và 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 đến , từ đến , và cứ thế).
Đầu phía tây của Phố Chính ở vị trí , 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 (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á .
Ràng buộc
- .
- , các giá trị tăng chặt.
- , và .
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ỳ . Xe đến đèn ở thời điểm và bị dừng khi , xác suất . Xe qua được đèn thì cũng qua được đèn , vì . |
| 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ó , luôn đỏ, nên xe chắc chắn phải dừng ở đâu đó. |
Bình luận