QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133941#6264. Lucky DrawKhNURE_KIVI#WA 2ms5108kbC++143.2kb2023-08-02 17:51:562023-08-02 17:52:14

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 17:52:14]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 5108kb
  • [2023-08-02 17:51:56]
  • Submitted

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef LOCAL
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
inline bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL

const int max_n = 201, inf = 1000111222;

ld dp[max_n][max_n] = {}, C[max_n][max_n] = {};


int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, k,  n;
    ld p;
    cin >> n >> k >> p;
    vector <ld> d(n + 1), P(n + 1), PP(n + 1);
    PP[0] = P[0] = 1;
    C[0][0] = 1;
    for (int i = 1; i < max_n; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] * p;
        PP[i] = PP[i - 1] * (1 - p);
    }
    d[0] = 1;
    d[1] = 0;
    cout << fixed;
    cout.precision(10);
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i] += d[i - j] * PP[j] * P[i - j];
        }
        d[i] /= 1 - P[i];
    }
    ld ans = 0;
    cout << fixed;
    cout.precision(10);
    dp[0][k] = 1;
    for (int i = 0; i + 1 < max_n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i + 1][j] += dp[i][j] * p;
            dp[i + 1][j - 1] += dp[i][j] * (1 - p);
        }
    }
    ld bad = 0;
    vector <ld> BB(n + 1);
    for (int day = 0; day < max_n; day++) {
        bad += dp[day][0];
        ld good = dp[day][1];
        ld GG = good;
        BB[0] = 1;
        for (int j = 1; j <= n; j++) {
            BB[j] = BB[j - 1] * bad;
        }
        for (int cnt = 2; cnt <= n; cnt++) {
            GG *= good;
            ans += C[n][cnt] * GG * BB[n - cnt] * PP[cnt];
        }
    }
    cout << ans << '\n';
    LOG(d[n]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4976kb

input:

2 2 0.5

output:

0.1851851852

result:

ok found '0.1851852', expected '0.1851852', error '0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 5108kb

input:

2 2 0.8

output:

0.0562414266

result:

ok found '0.0562414', expected '0.0562414', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4916kb

input:

5 3 0.85

output:

0.0454639641

result:

ok found '0.0454640', expected '0.0454640', error '0.0000000'

Test #4:

score: 0
Accepted
time: 2ms
memory: 5016kb

input:

10 1 0.1

output:

0.5591865022

result:

ok found '0.5591865', expected '0.5591865', error '0.0000000'

Test #5:

score: 0
Accepted
time: 2ms
memory: 5104kb

input:

10 1 0.5

output:

0.2787543425

result:

ok found '0.2787543', expected '0.2787543', error '0.0000000'

Test #6:

score: 0
Accepted
time: 2ms
memory: 4968kb

input:

10 1 0.9

output:

0.0508778419

result:

ok found '0.0508778', expected '0.0508778', error '0.0000000'

Test #7:

score: 0
Accepted
time: 2ms
memory: 5104kb

input:

10 2 0.1

output:

0.5327341098

result:

ok found '0.5327341', expected '0.5327341', error '0.0000000'

Test #8:

score: 0
Accepted
time: 2ms
memory: 5016kb

input:

10 2 0.5

output:

0.2268908997

result:

ok found '0.2268909', expected '0.2268909', error '0.0000000'

Test #9:

score: 0
Accepted
time: 2ms
memory: 4916kb

input:

10 2 0.9

output:

0.0391649075

result:

ok found '0.0391649', expected '0.0391649', error '0.0000000'

Test #10:

score: 0
Accepted
time: 2ms
memory: 5108kb

input:

10 3 0.1

output:

0.5230588549

result:

ok found '0.5230589', expected '0.5230589', error '0.0000000'

Test #11:

score: 0
Accepted
time: 0ms
memory: 5104kb

input:

10 3 0.5

output:

0.1993673560

result:

ok found '0.1993674', expected '0.1993674', error '0.0000000'

Test #12:

score: 0
Accepted
time: 2ms
memory: 5040kb

input:

10 3 0.9

output:

0.0335953024

result:

ok found '0.0335953', expected '0.0335953', error '0.0000000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 4920kb

input:

10 50 0.1

output:

0.2312509917

result:

ok found '0.2312510', expected '0.2312510', error '0.0000000'

Test #14:

score: 0
Accepted
time: 2ms
memory: 4924kb

input:

10 50 0.5

output:

0.0670958172

result:

ok found '0.0670958', expected '0.0670958', error '0.0000000'

Test #15:

score: -100
Wrong Answer
time: 1ms
memory: 5108kb

input:

10 50 0.9

output:

0.0000000000

result:

wrong answer 1st numbers differ - expected: '0.0103572', found: '0.0000000', error = '0.0103572'