QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133941 | #6264. Lucky Draw | KhNURE_KIVI# | WA | 2ms | 5108kb | C++14 | 3.2kb | 2023-08-02 17:51:56 | 2023-08-02 17:52:14 |
Judging History
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'