trang chủ / đề bài / icpcwf20_l

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×n ô, mỗi ô chứa 0 hoặc 1 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 m, n, t và q: m và n là kích thước bãi mìn, t là tổng số quả mìn, q là số truy vấn.

Dòng thứ hai chứa m số thực p1,p2,…,pm, dòng thứ ba chứa n số thực q1,q2,…,qn. Xác suất các kỹ sư đặt một quả mìn vào ô (i,j) là pi+qj. Mọi quyết định có đặt mìn vào từng ô hay không đều độc lập với nhau, và t được chọn sao cho xác suất đặt đúng t quả mìn ít nhất là 10−5.

Mỗi dòng trong q 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 s, tiếp theo là s cặp số nguyên i và j, là tọa độ của s ô đôi một khác nhau trong lưới.

Dữ liệu ra

Với mỗi truy vấn gồm s ô, in ra trên một dòng s+1 số thực: xác suất để s ô đã cho chứa tổng cộng 0,1,…,s quả mìn, biết rằng cả bãi có đúng t quả mìn. 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≤m,n≤500, 0≤t≤mn, 0≤q≤500.
  • 0≤pi≤0,1 và 0≤qj≤0,1, mỗi số có không quá sáu chữ số sau dấu thập phân.
  • Xác suất có đúng t quả mìn ít nhất là 10−5.
  • 0≤s≤500, 1≤i≤m, 1≤j≤n; 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 0,1, cả bãi có đúng 1 quả mìn nên quả mìn nằm ở mỗi ô với xác suất như nhau 14. Truy vấn 1: ô (1,1) có mìn với xác suất 0,25. Truy vấn 2: hai ô (2,1) và (1,2) chứa 1 quả mìn với xác suất 24=0,5, không thể chứa 2 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ó 3 quả mìn, nên tập 8 ô ở truy vấn cuối không thể chứa từ 4 quả trở lên.

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