Đa Số Tín Hiệu · canuc80k5501 · Thuật toán Canuc80k

Một hệ thống nhận dữ liệu từ $N$ cảm biến hoạt động độc lập, trong đó $N$ là số lẻ. Cảm biến thứ $i$ gửi tín hiệu dương với xác suất $p_{i}$ ; nếu không, nó gửi tín hiệu âm với xác suất $1 - p_{i}$ .

Sau khi tất cả cảm biến gửi đúng một tín hiệu, hệ thống chấp nhận khi số tín hiệu dương lớn hơn số tín hiệu âm. Hãy tính xác suất hệ thống chấp nhận.

Input

Dòng thứ nhất chứa số nguyên lẻ $N$ .
Dòng thứ hai chứa $N$ số thực $p_{1}, p_{2}, \dots, p_{N}$ , viết ở dạng thập phân. Các số này lần lượt là xác suất gửi tín hiệu dương của từng cảm biến.

Output

In một số thực là xác suất hệ thống chấp nhận. Kết quả được chấp nhận nếu sai số tuyệt đối không vượt quá $1 0^{- 9}$ .

Constraints

$1 \leq N \leq 2999$ và $N$ là số lẻ.
$0 < p_{i} < 1$ với mọi $1 \leq i \leq N$ .
Các cảm biến hoạt động độc lập với nhau.

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 19$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

3
0.20 0.50 0.90

Output

0.550000000000

Giải thích: Hệ thống chấp nhận khi có ít nhất hai tín hiệu dương. Xác suất có đúng hai tín hiệu dương là $0, 46$ , còn xác suất cả ba tín hiệu đều dương là $0, 09$ , nên kết quả bằng $0, 46 + 0, 09 = 0, 55$ .

Hướng giải: Sau khi xử lý một số cảm biến, đặt dp[k] là xác suất đã nhận được đúng k tín hiệu dương.
Hướng giải: Ban đầu chưa có tín hiệu nào, vì vậy dp[0] = 1. Khi xét cảm biến có xác suất gửi tín hiệu dương bằng p, một trạng thái mới có đúng k tín hiệu dương được tạo bởi hai trường hợp rời nhau:
Hướng giải: trước đó đã có k tín hiệu dương và cảm biến mới gửi tín hiệu âm, đóng góp dp[k] * (1 - p);
Hướng giải: trước đó đã có k - 1 tín hiệu dương và cảm biến mới gửi tín hiệu dương, đóng góp dp[k - 1] * p.
Hướng giải: Do đó công thức chuyển là
Hướng giải:

text new_dp[k] = dp[k] * (1 - p) + dp[k - 1] * p. - Hướng giải: Mã nguồn dùng một mảng và cập nhật k theo thứ tự giảm dần, nhờ vậy dp[k - 1] vẫn là giá trị của bước trước. Vì N lẻ, hệ thống chấp nhận chính xác khi số tín hiệu dương ít nhất là N / 2 + 1; ta cộng các trạng thái tương ứng. - Chứng minh đúng: Ta chứng minh bằng quy nạp theo số cảm biến đã xử lý rằng dp[k] bằng xác suất có đúng k tín hiệu dương. Mệnh đề đúng trước khi xử lý cảm biến nào vì chỉ trạng thái k = 0 có xác suất 1. Khi thêm một cảm biến, hai trường hợp tín hiệu âm và tín hiệu dương rời nhau, phủ hết mọi khả năng và có đúng các xác suất trong công thức chuyển. Vì thế bất biến được bảo toàn. Sau N bước, cộng mọi dp[k] với k > N/2 cho đúng xác suất của biến cố hệ thống chấp nhận. - Độ phức tạp: Thuật toán dùng O(N^2) thời gian và O(N) bộ nhớ.