Atcoder Educational DP Contest I - Coins

Xem dạng PDF
Gửi bài giải
Điểm: 0,30 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout
Người đăng:
ncduy0303
Nguồn bài:
Atcoder Educational DP Contest
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ~N~ là một số nguyên dương lẻ.

Có tất cả ~N~ đồng xu được đánh số ~1,2,...,N~. Xác suất để đồng xu thứ ~i~ ~(1 \leq i \leq N)~ lật mặt ngửa khi được tung lên là ~p_{i}~ và xác suất để nó lật mặt sấp khi được tung lên là ~1-p_{i}~.

Taro sẽ tung hết tất cả ~N~ đồng xu. Tìm xác suất để có số mặt ngửa nhiều hơn số mặt sấp.

Input

Dòng đầu tiên chứa số nguyên dương lẻ ~N~ ~(1 \leq N \leq 2999)~

Dòng tiếp theo chứa ~N~ số thực ~p_{i}~ ~(0 < p_{i} < 1)~, mỗi số có hai chữ số thập phân.

Output

In ra xác suất để có số mặt ngửa nhiều hơn số mặt sấp. Kết quả in ra được coi là chính xác nếu sai số tuyệt đối với đáp án không vượt quá ~10^{-9}~.

Sample 1

Input
3
0.30 0.60 0.80
Output
0.612
Giải thích

Xác suất để có số mặt ngửa nhiều hơn số mặt sấp bao gồm các trường hợp:

  • Xác suất để có (Ngửa, Ngửa, Ngửa) là ~0.3×0.6×0.8=0.144~;
  • Xác suất để có (Sấp, Ngửa, Ngửa) là ~0.7×0.6×0.8=0.336~;
  • Xác suất để có (Ngửa, Sấp, Ngửa) là ~0.3×0.4×0.8=0.096~;
  • Xác suất để có (Ngửa, Ngửa, Sấp) là ~0.3×0.6×0.2=0.036~.

Do đó, xác suất để có số mặt ngửa nhiều hơn số mặt sấp là ~0.144+0.336+0.096+0.036=0.612~.

Sample 2

Input
1
0.50
Output
0.5
Giải thích:

Kết quả in ra ví dụ như 0.500, 0.500000001 and 0.499999999 đều được coi là chình xác.

Sample 3

Input
5
0.42 0.01 0.42 0.99 0.42
Output
0.3821815872

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 1
    vominhmanh10  đã bình luận lúc 15, Tháng 11, 2025, 13:19 ← sửa 4

    à có thể làm rõ lời giải bài này một chút, ta giải bằng dp xác xuất cho nó, có 2 trạng thái là tới đồng xu i và có bao nhiêu mặt ngửa dp[i][j]
    khi tới đồng xu i, có 2 khả năng là sấp và ngửa nên
    ngửa: sẽ chèn thêm từ dp[i - 1][j - 1] * a[i] xác xuất
    sấp: xác xuất sấp là 1 - a[i] sẽ chèn thêm từ dp[i - 1][j] * (1 - a[i]) xác xuất
    kết quả: dp[i][j] = dp[i - 1][j - 1] * a[i] + dp[i - 1][j] * (1 - a[i])

    import sys
input = sys.stdin.readline

def main():
    dp[0] = 1
    for i in range(1, n + 1):
        p = a[i - 1]
        for j in range(i, -1, -1):
            dp[j] = dp[j - 1] * p + dp[j] * (1 - p)
    return sum(dp[i] for i in range(n // 2 + 1, n + 1))


n = int(input())
a = list(map(float, input().split()))
dp = [0] * (n + 1)
print(f"{main():.9f}")

  • -2
    nmk05022006  đã bình luận lúc 1, Tháng 10, 2025, 14:51

    hay


  • -2
    tunbeo2021  đã bình luận lúc 29, Tháng 9, 2025, 10:22

    hay


  • -2
    deanqkhanh  đã bình luận lúc 28, Tháng 9, 2025, 6:33

    hay


  • -16
    tungdao123pzo  đã bình luận lúc 25, Tháng 5, 2024, 7:55

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 2
    ngthang2022  đã bình luận lúc 16, Tháng 12, 2023, 8:32

    nể admin ác =)))


  • -4
    duongnguyen0210  đã bình luận lúc 25, Tháng 11, 2023, 5:57

    code sol lú vl =))))


  • -4
    tonblan  đã bình luận lúc 15, Tháng 11, 2023, 19:22

    vl sao may ong toan de avt gai the


    • -7
      yuyuuend  đã bình luận lúc 1, Tháng 12, 2023, 15:14

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 1
    Cuunon311  đã bình luận lúc 9, Tháng 10, 2023, 12:31

    bai nay hay


  • -3
    dangduc2102  đã bình luận lúc 2, Tháng 8, 2023, 16:33

    adu bai nay hay qua ae