Trúng thưởng bãi mìn
Đề bài
Mô tả
Bạn có thể đã trúng thưởng! Thật ra, bạn đã trúng thưởng rồi! Phần thưởng là một hòn đảo của riêng bạn, ở nơi sâu thẳm nhất của đại dương chưa ai khám phá. À, gần như chưa ai khám phá. Trước bạn, trên đảo có một căn cứ quân sự nhỏ; khi rút đi, họ để lại đủ thứ: phế liệu, đạn dược, đường hầm, ... và cả mìn phòng thủ chưa nổ.
Đúng vậy: giờ bạn sở hữu một bãi mìn của riêng mình.
Bãi mìn là một lưới ô, mỗi ô chứa hoặc quả mìn. May mắn là bạn tìm lại được bản kế hoạch của các kỹ sư khi họ đặt mìn. Không may là vị trí chính xác của các quả mìn chưa bao giờ được ghi lại: các kỹ sư chọn trước một xác suất đặt mìn cho mỗi ô, và các ô được quyết định độc lập với nhau. Tuy vậy, bạn biết tổng số quả mìn đã được đặt.
Bạn muốn ước lượng mức độ an toàn của từng phần trên đảo. Hãy viết chương trình tính xác suất của số quả mìn trên các tập ô khác nhau của bãi mìn.
Dữ liệu vào
Dòng đầu tiên chứa bốn số nguyên , , và : và là kích thước bãi mìn, là tổng số quả mìn, là số truy vấn.
Dòng thứ hai chứa số thực , dòng thứ ba chứa số thực . Xác suất các kỹ sư đặt một quả mìn vào ô là . Mọi quyết định có đặt mìn vào từng ô hay không đều độc lập với nhau, và được chọn sao cho xác suất đặt đúng quả mìn ít nhất là .
Mỗi dòng trong dòng còn lại mô tả một truy vấn. Dòng bắt đầu bằng một số nguyên , tiếp theo là cặp số nguyên và , là tọa độ của ô đôi một khác nhau trong lưới.
Dữ liệu ra
Với mỗi truy vấn gồm ô, in ra trên một dòng số thực: xác suất để ô đã cho chứa tổng cộng quả mìn, biết rằng cả bãi có đúng quả mìn. Mỗi số được chấp nhận nếu sai số tuyệt đối không quá .
Ràng buộc
- , , .
- và , mỗi số có không quá sáu chữ số sau dấu thập phân.
- Xác suất có đúng quả mìn ít nhất là .
- , , ; các ô trong một truy vấn đôi một khác nhau.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 1 2 0.05 0.05 0.05 0.05 1 1 1 2 2 1 1 2 |
0.75 0.25 0.5 0.5 0 |
Mọi ô có xác suất , cả bãi có đúng quả mìn nên quả mìn nằm ở mỗi ô với xác suất như nhau . Truy vấn : ô có mìn với xác suất . Truy vấn : hai ô và chứa quả mìn với xác suất , không thể chứa quả. |
| 3 4 3 4 0.02 0.04 0.06 0.005 0.07 0.035 0.09 1 3 2 3 1 4 2 4 3 4 4 1 2 2 3 3 1 1 4 8 1 1 1 2 1 3 2 1 2 3 3 1 3 2 3 3 |
0.649469772 0.350530228 0.219607636 0.527423751 0.237646792 0.015321822 0.267615440 0.516222318 0.201611812 0.014550429 0 0.054047935 0.364731941 0.461044157 0.120175967 0 0 0 0 0 |
Cả bãi có quả mìn, nên tập ô ở truy vấn cuối không thể chứa từ quả trở lên. |
Bình luận