Bài toán đồng xu 1

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Thời gian:
Python 3 10.0s
Bộ nhớ:
Python 3 293M
Tác giả:
jumptozero
Dạng bài
Điểm: 500 Thời gian: 4.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Có \(N\) đồng xu, được đánh số \(1,2,3,\cdots,N\). Với mỗi \(i(1 \leq i \leq N)\), khi đồng xu \(i\) được gieo, xác suất nó xảy ra mặt ngửa là \(p_i\) và xác suất nó xảy ra mặt úp là \(1−p_i\).

Kaninho gieo \(N\) đồng xu cùng một lúc. Tính xác suất để ta thu được số lượng đồng xu ngửa lớn hơn số lượng đồng xu úp.

Input

  • Dòng thứ nhất chứa số nguyên dương lẻ \(N(1 \leq N \leq 2999)\)
  • Dòng thứ hai chứa \(n\) số thực có 2 chữ số ở hàng thập phân \(p_i(0<p_i<1)\)

Output

  • In ra đáp án cần tìm. (Gọi \(x\) là đáp án của bạn, \(y\) là đáp án của bài toán, thì \(x\) được chấp nhận là đúng nếu \(|x−y|<10^{−9}\))

Example

Test 1

Input 
3
0.30 0.60 0.80
Output 
0.612
Note

Xác suất của mỗi trường hợp có số lượng đồng xu ngửa lớn hơn số lượng đồng xu úp là :

\(P(ngua,ngua,ngua)\)=\(0.3∗0.6∗0.8=0.144\)
\(P(up,ngua,ngua)\)=\(0.7∗0.6∗0.8=0.336\)
\(P(ngua,up,ngua)\)=\(0.3∗0.4∗0.8=0.096\)
\(P(ngua,ngua,up)\)=\(0.3∗0.6∗0.2=0.036\)
Như vậy, xác suất có số lượng mặt ngửa lớn hơn số lượng đồng xu úp là: \(0.144+0.336+0.096+0.036=0.612\)

Bình luận


  • 13
    NguyenHuuNhatQuang    8:33 p.m. 22 Tháng 8, 2020 ← chỉnh sửa 4

    Hint

    Bài này thực ra có 3 cách để quy hoạch động

    Cách 1

    Gọi \(dp[i][j]\) là xác suất khi tung \(i\) đồng xu đầu tiên được \(j\) đồng xu ngửa.

    Trường hợp 1: Đồng xu \(i\) là đồng ngửa => Ta cần tính xác suất để tung \(i-1\) đồng đầu tiên được \(j-1\) đồng ngửa. Vậy xác suất cho trường hợp này là \(dp[i-1][j-1]*p[i]\).

    Trường hợp 2: Đồng xu \(i\) là đồng sấp => Ta cần tính xác suất để tung \(i-1\) đồng đầu tiên được \(j\) đồng ngửa. Vậy xác suất cho trường hợp này là \(dp[i-1][j]*(1-p[i])\).

    Vậy xác suất để tung \(i\) đồng được \(j\) đồng ngửa là \(dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i])\)

    Xác suất để tung \(n\) đồng được số đồng ngửa nhiều hơn số đồng sấp là \(dp[n][n/2+1]+dp[n][n/2+2]+...+dp[n][n]\)

    AC code

    #include<bits/stdc++.h>
using namespace std;
double dp[3005][3005];
int main()
{
    cout.precision(9);
    int n;
    cin>>n;
    double p;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        for(int j=0;j<=i;j++)
            dp[i][j]=dp[i-1][j-1]*p+dp[i-1][j]*(1-p);
    }
    p=0;
    for(int i=n/2+1;i<=n;i++) p+=dp[n][i];
    cout<<p;
}

    Cách 2 ##

    (Hơi phức tạp hơn tý)

    Gọi \(dp[i][j]\) là xác suất khi tung \(i\) đồng xu đầu tiên được số đồng xu ngửa nhiều hơn số đồng xu sấp \(j\) đồng (\(j\) có thể âm).

    Trường hợp 1: Đồng xu \(i\) là đồng ngửa => Ta cần tính xác suất để tung \(i-1\) đồng đầu tiên được số đồng ngửa nhều hơn số đồng sấp là \(j-1\) đồng. Vậy xác suất cho trường hợp này là \(dp[i-1][j-1]*p[i]\).

    Trường hợp 2: Đồng xu \(i\) là đồng sấp => Ta cần tính xác suất để tung \(i-1\) đồng đầu tiên được số đồng ngửa nhiều hơn số đồng sấp là \(j+1\) đồng. Vậy xác suất cho trường hợp này là \(dp[i-1][j+1]*(1-p[i])\).

    Vậy xác suất để tung \(i\) đồng được \(j\) đồng ngửa là \(dp[i-1][j-1]*p[i]+dp[i-1][j+1]*(1-p[i])\)

    Xác suất để tung \(n\) đồng được số đồng ngửa nhiều hơn số đồng sấp là \(dp[n][1]+dp[n][2]+...+dp[n][n]\)

    AC code

    #include<bits/stdc++.h>
using namespace std;
double dp[3005][6005];
int main()
{
    cout.precision(9);
    int n;
    cin>>n;
    dp[0][3000]=1;
    double p;
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        for(int j=-i;j<=i;j++)
            dp[i][j+3000]=dp[i-1][j+2999]*p+dp[(i-1)][j+3001]*(1-p);
    }
    double t=0;
    for(int i=0;i<=n;i++)
        t+=dp[n][i+3000];
    cout<<t;
}

    Cách 3

    (Khó code nhất nhưng dễ hiểu nhất)

    Gọi \(dp[i][j]\) là xác suất khi tung \(i+j\) đồng xu đầu tiên được \(i\) đồng xu ngửa và \(j\) đồng xu sấp.

    Trường hợp 1: Đồng xu \(i+j\) là đồng ngửa => Ta cần tính xác suất để tung \(i+j-1\) đồng đầu tiên được \(i-1\) đồng ngửa và \(j\) đồng sấp. Vậy xác suất cho trường hợp này là \(dp[i-1][j]*p[i]\).

    Trường hợp 2: Đồng xu \(i+j\) là đồng sấp => Ta cần tính xác suất để tung \(i+j-1\) đồng đầu tiên được \(i\) đồng ngửa và \(j-1\) đồng sấp. Vậy xác suất cho trường hợp này là \(dp[i][j-1]*(1-p[i])\).

    Vậy xác suất để tung \(i\) đồng được \(j\) đồng ngửa là \(dp[i-1][j]*p[i]+dp[i][j-1]*(1-p[i])\)

    Xác suất để tung \(n\) đồng được số đồng ngửa nhiều hơn số đồng sấp là \(dp[n/2+1][n/2]+dp[n/2+2][n/2-1]+...+dp[n][0]\)

    AC code

    #include<bits/stdc++.h>
using namespace std;
double dp[3005][3005];
double rat[3005];
int main()
{
    cout.precision(9);
    int n;
    cin>>n;
    double p;
    dp[0][0]=1;
    for(int i=1;i<=n;i++) cin>>rat[i];
    for(int i=0;i<=n;i++)
    {
        for(int j=0+(i==0);j<=n-i;j++)
        {
            double t=dp[i-1][j];
            if(i==0) t=0;
            dp[i][j]=t*rat[i+j]+dp[i][j-1]*(1-rat[i+j]);
        }
    }
    p=0;
    for(int i=n/2+1;i<=n;i++) p+=dp[i][n-i];
    cout<<p;
}

    Ghi chú: Ta dùng lệnh cout.precision(9) để lấy đến 9 chữ số sau dấu thập phân.
    Độ phức tạp của 3 cách này đều là \(O(N^2)\)

      • 5 bình luận nữa