SGAME5

Tác giả:

Dạng bài

Ngôn ngữ cho phép

~~Assembly~~, Awk, C, C#, C++, Clang, Clang++, Cobol, D, Groovy, ~~Haskell~~, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Pascal, Perl, PHP, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 500 (p) Thời gian: 0.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

SPyofgame là một điệp viên của tổ chức O.W.C.A với bí danh H (H là gì thì chắc ai cũng nhận ra). Mỗi tháng, anh ta nhận được một danh sách nhiệm vụ của mình. Dù là thành viên lâu năm nhưng SPyofgame khá lười biếng, suốt ngày chỉ lo chơi surviv và nhắn tin cho bạn gái, anh ta không thể tính toán được xác suất để hoàn thành được \(N\) nhiệm vụ cụ thể được giao nên thường bị phạt tiền. Lần này, bạn hãy giúp anh ấy tính xác suất để anh ấy có thể hoàn thành được nhiệm vụ.

Input

Dòng đầu tiên là số nguyên dương \(N\), số lượng nhiệm vụ được giao \((1 \leq N \leq 20)\)
\(N\) dòng tiếp theo, mỗi dòng bao gồm \(N\) số nguyên dương \(x\) là xác xuất(%) để hoàn thành được nhiệm vụ con thứ \(i\) \((1 \leq i \leq N, 0 \leq x \leq 100)\)

Output

1 dòng duy nhất là xác suất để SPyofgame có thể hoàn thành \(N\) nhiệm vụ, đáp án được chấp nhận nếu sai số không quá \(10^{-6}\)

Example

Test 1

Input

Output

0.150000000000

Note

Ở nhiệm vụ 1, SPyofgame có thể nhận nhiệm vụ con thứ 2 với xác suất thành công là \(6\)%
Ở nhiệm vụ 2, SPyofgame có thể nhận nhiệm vụ con thứ 3 với xác suất thành công là \(10\)%
Ở nhiệm vụ 3, SPyofgame có thể nhận nhiệm vụ con thứ 1 với xác suất thành công là \(25\)%

→ Tổng xác suất thành công của nhiệm vụ là 0.06 x 0.1 x 0.25 = 0.0015 = 0.15%

Không có cách nhận nhiệm vụ nào có xác suất thành công cao hơn 0.15%

Giới hạn:

Subtask 1: 25% số test có N ≤ 5
Subtask 2: 50% số test có N ≤ 10
Subtask 3: 75% số test có N ≤ 15
Subtask 4: không có giới hạn gì thêm

Bình luận

0

BeTapDi 7:43 a.m. 2 Tháng 8, 2020

a vinh ơi e không hiểu đề ạ, a giải thick giúp e vs (mà nhìn n thì đoán là bitmask :v) .-.

2

vinhntndu 8:29 a.m. 2 Tháng 8, 2020

có thể hiểu bài này là có a1, a2, a3, ... an nhiệm vụ 1, b1, b2, b3, ... bn nhiệm vụ 2, ...
chọn nhiệm vụ sao cho chỉ số không trùng nhau (ví dụ a1, b2, c3, ...) sao cho a1b2c3*... là lớn nhất

1

vinhntndu 8:21 a.m. 2 Tháng 8, 2020 ← đã chỉnh sửa →

bài này bit j đâu, mà thực ra bitmask cho nhanh cũng đc

1

vinhntndu 8:16 a.m. 2 Tháng 8, 2020 ← đã chỉnh sửa →

có N nhiệm vụ lớn, mỗi nhiệm vụ lớn có N nhiệm vụ nhỏ với xác suất là a[i]%. chọn các nhiệm vụ nhỏ (không trùng nhau) sao cho hoàn thành được tất cả N nhiệm vụ lớn với xác suất cao nhất

0

BeTapDi 8:53 a.m. 2 Tháng 8, 2020

ý em là test vd hình như giải thick sai á a, đọc ví dụ mãi k hỉu 🙂

0

tuandq 2:51 p.m. 2 Tháng 8, 2020

Nhưng mà em thấy trường hợp đó chưa phải là tối ưu nhất. Ở nhiệm vụ 1, SPyofgame có thể nhận nhiệm vụ con thứ 1 (6%). Ở nhiệm vụ 2, SPyofgame có thể nhận nhiệm vụ con thứ 3 (10%). Ở nhiệm vụ 3, SPyofgame có thể nhận nhiệm vụ con thứ 1 (25%). Vậy thì tổng xác xuất thành công của nhiệm vụ là: 0.1 x 0.1 x 0.25 = 0.0025 = 0.25%, cao hơn 0.15%.

0

hhoangcpascal 3:18 p.m. 2 Tháng 8, 2020

thế nhiệm vụ con thứ 2 đâu?

0

tuandq 8:22 p.m. 2 Tháng 8, 2020

Ở nhiệm vụ 2, SPyofgame có thể nhận nhiệm vụ con thứ 3 (10%).

0

vinhntndu 8:47 p.m. 2 Tháng 8, 2020

tính lại đi, k còn cách nào đâu

1

vinhntndu 8:44 p.m. 2 Tháng 8, 2020

Ở nhiệm vụ 2, SPyofgame có thể nhận nhiệm vụ con thứ 3 (10%) thì giống đề r

3
vinhntndu 9:11 a.m. 2 Tháng 8, 2020
à chỗ giải thích a sinh test xong nhầm ấy, là

Ở nhiệm vụ 1, SPyofgame có thể nhận nhiệm vụ con thứ 2 (a2) với xác suất thành công là 6%

Ở nhiệm vụ 2, SPyofgame có thể nhận nhiệm vụ con thứ 3 (b3)với xác suất thành công là 10%

Ở nhiệm vụ 3, SPyofgame có thể nhận nhiệm vụ con thứ nhất (c1) với xác suất thành công là 25%

6 bình luận nữa