QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#384243 | #4687. Weather Report | Energy_is_not_over# | AC ✓ | 32ms | 4248kb | C++17 | 2.9kb | 2024-04-09 21:07:34 | 2024-04-09 21:07:35 |
Judging History
answer
//
// Stvoreno ENERGom o 09.04.24. 14:46:54
//
#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define MP make_pair
#define pb push_back
#define PB push_back
#define F first
#define fir first
#define S second
#define sec second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef __float128 ld;
#ifdef Energy
#define DEBUG for (int ____DEBUG=1;____DEBUG;____DEBUG=0)
template<class ...Ts>
auto &PRNT(Ts ...ts) { return ((cerr << ts << " "), ...); }
#define LOG(...) PRNT(#__VA_ARGS__" ::",__VA_ARGS__)<<endl
#else
#define DEBUG while(0)
#define LOG(...)
#endif
const int max_n = 22, inf = 1000111222;
int n;
long double p[4];
ll c[max_n][max_n];
ll calc_ways(int A, int B, int C, int D) {
return c[n][A] * c[n - A][B] * c[n - A - B][C];
}
ld mypow(ld x, int n) {
ld res = 1;
while (n--) {
res *= x;
}
return res;
}
int main() {
// freopen("input_l.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < max_n; ++i) {
c[i][0] = 1;
for (int j = 1; j <= i; ++j) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
}
cin >> n >> p[0] >> p[1] >> p[2] >> p[3];
multiset<pair<ld, ll>> q;
for (int a = 0; a <= n; ++a) {
for (int b = 0; a + b <= n; ++b) {
for (int c = 0; a + b + c <= n; ++c) {
const int d = n - a - b - c;
ll ways = calc_ways(a, b, c, d);
ld prob = 1;
if (a) {
prob *= mypow(p[0], a);
}
if (b) {
prob *= mypow(p[1], b);
}
if (c) {
prob *= mypow(p[2], c);
}
if (d) {
prob *= mypow(p[3], d);
}
// LOG(a, b, c, d, prob, ways);
q.insert({prob, ways});
}
}
}
LOG(q.size());
ld ans = 0;
while (!q.empty()) {
auto [prob, ways] = *q.begin();
// LOG(prob, ways);
q.erase(q.begin());
if (ways >= 2) {
ans += 2 * prob * (ways / 2);
q.insert({2 * prob, ways / 2});
if (ways % 2) {
q.insert({prob, 1});
}
} else {
if (q.empty()) {
break;
}
auto [prob2, ways2] = *q.begin();
// LOG(prob2, ways2);
ans += (prob + prob2);
q.erase(q.begin());
q.insert({prob + prob2, 1});
if (ways2 > 1) {
q.insert({prob2, ways2 - 1});
}
}
}
cout << fixed << setprecision(10) << (long double) ans << "\n";
exit(0);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3968kb
input:
2 0.9 0.049999 0.05 0.000001
output:
1.4575099500
result:
ok found '1.45751', expected '1.45751', error '0.00000'
Test #2:
score: 0
Accepted
time: 30ms
memory: 4244kb
input:
20 0.25 0.25 0.25 0.25
output:
40.0000000000
result:
ok found '40.00000', expected '40.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 25ms
memory: 4016kb
input:
19 0.5 0.3 0.08615 0.11385
output:
32.0000551029
result:
ok found '32.00006', expected '32.00006', error '0.00000'
Test #4:
score: 0
Accepted
time: 25ms
memory: 4100kb
input:
19 0.255 0.265 0.235 0.245
output:
37.9943446614
result:
ok found '37.99434', expected '37.99435', error '0.00000'
Test #5:
score: 0
Accepted
time: 30ms
memory: 3984kb
input:
20 0.066667 0.133333 0.266667 0.533333
output:
32.8488848021
result:
ok found '32.84888', expected '32.84889', error '0.00000'
Test #6:
score: 0
Accepted
time: 27ms
memory: 4248kb
input:
20 0.27 0.26 0.24 0.23
output:
39.9700244231
result:
ok found '39.97002', expected '39.97002', error '0.00000'
Test #7:
score: 0
Accepted
time: 32ms
memory: 4120kb
input:
20 0.5 0.2 0.175 0.125
output:
35.6177332358
result:
ok found '35.61773', expected '35.61773', error '0.00000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
2 0.9 0.05 0.049999 0.000001
output:
1.4575099500
result:
ok found '1.45751', expected '1.45751', error '0.00000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 0.25 0.25 0.25 0.25
output:
6.0000000000
result:
ok found '6.00000', expected '6.00000', error '0.00000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
9 0.25 0.25 0.25 0.25
output:
18.0000000000
result:
ok found '18.00000', expected '18.00000', error '0.00000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3976kb
input:
9 0.1 0.4 0.3 0.2
output:
16.6459855790
result:
ok found '16.64599', expected '16.64599', error '0.00000'
Test #12:
score: 0
Accepted
time: 30ms
memory: 4124kb
input:
20 0.56 0.1 0.01 0.33
output:
27.9269671936
result:
ok found '27.92697', expected '27.92697', error '0.00000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
1 0.5 0.25 0.125 0.125
output:
1.7500000000
result:
ok found '1.75000', expected '1.75000', error '0.00000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
2 0.5 0.25 0.125 0.125
output:
3.5000000000
result:
ok found '3.50000', expected '3.50000', error '0.00000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3948kb
input:
3 0.5 0.25 0.125 0.125
output:
5.2500000000
result:
ok found '5.25000', expected '5.25000', error '0.00000'
Test #16:
score: 0
Accepted
time: 3ms
memory: 3992kb
input:
11 0.5 0.25 0.125 0.125
output:
19.2500000000
result:
ok found '19.25000', expected '19.25000', error '0.00000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
1 0.403 0.199 0.199 0.199
output:
1.9950000000
result:
ok found '1.99500', expected '1.99500', error '0.00000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
1 0.199 0.403 0.199 0.199
output:
1.9950000000
result:
ok found '1.99500', expected '1.99500', error '0.00000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
1 0.199 0.199 0.403 0.199
output:
1.9950000000
result:
ok found '1.99500', expected '1.99500', error '0.00000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
1 0.199 0.199 0.199 0.403
output:
1.9950000000
result:
ok found '1.99500', expected '1.99500', error '0.00000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
4 0.4 0.25 0.24 0.11
output:
7.5251345700
result:
ok found '7.52513', expected '7.52513', error '0.00000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
4 0.25 0.4 0.24 0.11
output:
7.5251345700
result:
ok found '7.52513', expected '7.52513', error '0.00000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
4 0.25 0.24 0.4 0.11
output:
7.5251345700
result:
ok found '7.52513', expected '7.52513', error '0.00000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
4 0.25 0.24 0.11 0.4
output:
7.5251345700
result:
ok found '7.52513', expected '7.52513', error '0.00000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
4 0.0001 0.0002 0.00034 0.99936
output:
1.0089885151
result:
ok found '1.00899', expected '1.00899', error '0.00000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
4 0.99936 0.00034 0.0002 0.0001
output:
1.0089885151
result:
ok found '1.00899', expected '1.00899', error '0.00000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
4 0.00034 0.99936 0.0002 0.0001
output:
1.0089885151
result:
ok found '1.00899', expected '1.00899', error '0.00000'
Test #28:
score: 0
Accepted
time: 27ms
memory: 4120kb
input:
20 0.000001 0.999997 0.000001 0.000001
output:
1.0003570084
result:
ok found '1.00036', expected '1.00036', error '0.00000'
Test #29:
score: 0
Accepted
time: 9ms
memory: 4068kb
input:
15 0.000001 0.000001 0.999997 0.000001
output:
1.0002520045
result:
ok found '1.00025', expected '1.00025', error '0.00000'
Test #30:
score: 0
Accepted
time: 21ms
memory: 3956kb
input:
18 0.01 0.345 0.345 0.3
output:
29.6750587434
result:
ok found '29.67506', expected '29.67506', error '0.00000'
Test #31:
score: 0
Accepted
time: 16ms
memory: 4132kb
input:
17 0.13 0.35 0.13 0.39
output:
31.0568361587
result:
ok found '31.05684', expected '31.05684', error '0.00000'
Test #32:
score: 0
Accepted
time: 31ms
memory: 4056kb
input:
20 0.14 0.33 0.14 0.39
output:
37.0670968886
result:
ok found '37.06710', expected '37.06710', error '0.00000'
Test #33:
score: 0
Accepted
time: 31ms
memory: 4004kb
input:
20 0.125001 0.25 0.5 0.124999
output:
35.0000000000
result:
ok found '35.00000', expected '35.00000', error '0.00000'
Test #34:
score: 0
Accepted
time: 31ms
memory: 3996kb
input:
20 0.01 0.34503 0.34503 0.29994
output:
32.9672035253
result:
ok found '32.96720', expected '32.96720', error '0.00000'
Test #35:
score: 0
Accepted
time: 28ms
memory: 4168kb
input:
20 0.4 0.2 0.3 0.1
output:
36.9592971671
result:
ok found '36.95930', expected '36.95930', error '0.00000'
Test #36:
score: 0
Accepted
time: 32ms
memory: 4040kb
input:
20 0.01 0.02 0.03 0.94
output:
8.3247096881
result:
ok found '8.32471', expected '8.32471', error '0.00000'
Test #37:
score: 0
Accepted
time: 29ms
memory: 4128kb
input:
20 0.991 0.003 0.003 0.003
output:
2.1213818217
result:
ok found '2.12138', expected '2.12138', error '0.00000'
Test #38:
score: 0
Accepted
time: 25ms
memory: 4020kb
input:
20 0.495 0.005 0.495 0.005
output:
21.6754013648
result:
ok found '21.67540', expected '21.67540', error '0.00000'
Test #39:
score: 0
Accepted
time: 28ms
memory: 3984kb
input:
20 0.492 0.008 0.493 0.007
output:
22.3229281448
result:
ok found '22.32293', expected '22.32293', error '0.00000'
Test #40:
score: 0
Accepted
time: 29ms
memory: 4020kb
input:
20 0.032 0.051 0.023 0.894
output:
12.9856549695
result:
ok found '12.98565', expected '12.98565', error '0.00000'
Test #41:
score: 0
Accepted
time: 29ms
memory: 4112kb
input:
20 0.002 0.01 0.09 0.898
output:
10.7619687926
result:
ok found '10.76197', expected '10.76197', error '0.00000'
Test #42:
score: 0
Accepted
time: 31ms
memory: 4116kb
input:
20 0.91 0.03 0.03 0.03
output:
11.6424469039
result:
ok found '11.64245', expected '11.64245', error '0.00000'