QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#29935 | #2913. Archery Accuracy | George_Plover# | AC ✓ | 84ms | 4872kb | C++23 | 1.9kb | 2022-04-23 14:48:01 | 2022-04-28 16:03:39 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, r, l) for (int i = r; i >= l; --i)
using namespace std;
typedef long long ll;
const int N = 17;
const int M = 1 << N;
struct matrix {
double a[2][2];
matrix operator*(const matrix &rhs) const {
matrix ret;
rep(i, 0, 1) {
rep(j, 0, 1) {
ret.a[i][j] = 0;
rep(k, 0, 1) { ret.a[i][j] += a[i][k] * rhs.a[k][j]; }
}
}
return ret;
}
matrix operator^(const int &k) const {
matrix m = *this;
matrix ret;
rep(i, 0, 1) rep(j, 0, 1) ret.a[i][j] = (i == j);
int y = k;
while (y) {
if (y & 1) ret = ret * m;
m = m * m;
y >>= 1;
}
return ret;
}
};
double f(int a, int b, double p) {
matrix m;
m.a[0][0] = 0, m.a[0][1] = 1;
m.a[1][0] = 1 - 1 / p, m.a[1][1] = 1 / p;
matrix mn = m ^ (a + b);
double x = 1 / mn.a[0][1];
matrix ma = m ^ a;
double ret = ma.a[0][1] * x;
// printf("f(%d,%d,%lf)=%lf\n", a, b, p, ret);
return ret;
}
int n;
double p[N];
int s[N];
double dp[M];
int main() {
scanf("%d", &n);
rep(i, 0, n - 1) { scanf("%lf", &p[i]); }
s[0] = 0;
rep(i, 1, n) { scanf("%d", &s[i]); }
dp[0] = 1;
rep(S, 1, (1 << n) - 1) {
int t = __builtin_popcount(S);
dp[S] = 0;
rep(i, 0, n - 1) {
if (S & (1 << i)) {
int S0 = S - (1 << i);
dp[S] = max(dp[S],
dp[S0] * f(s[t] + s[t - 1], s[t] - s[t - 1], p[i]) +
(1 - dp[S0]) *
f(s[t] - s[t - 1], s[t] + s[t - 1], p[i]));
}
}
// printf("%d %lf\n", S, dp[S]);
}
printf("%.8lf\n", dp[(1 << n) - 1]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 78ms
memory: 4784kb
input:
17 0.49 0.45 0.50 0.47 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.49 0.50 0.49 0.50 0.49 15 16 17 18 19 20 26 29 86 88 89 93 95 96 97 98 100
output:
0.45164222
result:
ok found '0.4516422', expected '0.4516422', error '0.0000000'
Test #2:
score: 0
Accepted
time: 77ms
memory: 4808kb
input:
17 0.50 0.50 0.50 0.50 0.47 0.49 0.50 0.50 0.50 0.49 0.39 0.51 0.46 0.49 0.50 0.50 0.50 1 65 67 68 69 70 71 78 79 84 90 91 94 95 96 97 100
output:
0.58093501
result:
ok found '0.5809350', expected '0.5809350', error '0.0000000'
Test #3:
score: 0
Accepted
time: 77ms
memory: 4728kb
input:
17 0.50 0.47 0.50 0.43 0.43 0.50 0.50 0.50 0.46 0.50 0.28 0.50 0.50 0.49 0.50 0.42 0.48 7 9 10 11 14 17 18 77 78 79 84 85 87 89 98 99 100
output:
0.40390034
result:
ok found '0.4039003', expected '0.4039003', error '0.0000000'
Test #4:
score: 0
Accepted
time: 56ms
memory: 4784kb
input:
17 0.50 0.50 0.50 0.47 0.50 0.52 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.48 0.50 0.49 3 4 6 7 8 9 10 11 15 73 75 76 80 81 82 89 100
output:
0.86095234
result:
ok found '0.8609523', expected '0.8609523', error '0.0000000'
Test #5:
score: 0
Accepted
time: 77ms
memory: 4868kb
input:
17 0.35 0.47 0.46 0.48 0.50 0.46 0.50 0.49 0.50 0.47 0.45 0.54 0.50 0.50 0.50 0.50 0.43 1 2 6 8 10 66 81 82 83 84 86 87 88 90 91 98 100
output:
0.77608821
result:
ok found '0.7760882', expected '0.7760882', error '0.0000000'
Test #6:
score: 0
Accepted
time: 63ms
memory: 4828kb
input:
17 0.50 0.50 0.50 0.50 0.47 0.50 0.50 0.46 0.50 0.49 0.46 0.50 0.50 0.49 0.50 0.5 0.49 1 7 9 10 12 14 15 16 18 19 81 83 84 85 86 87 100
output:
0.47504092
result:
ok found '0.4750409', expected '0.4750409', error '0.0000000'
Test #7:
score: 0
Accepted
time: 75ms
memory: 4800kb
input:
17 0.44 0.47 0.50 0.49 0.47 0.81 0.68 0.41 0.50 0.44 0.50 0.50 0.46 0.47 0.49 0.19 0.48 3 7 10 12 13 15 19 20 81 83 94 95 96 97 98 99 100
output:
0.98637639
result:
ok found '0.9863764', expected '0.9863764', error '0.0000000'
Test #8:
score: 0
Accepted
time: 74ms
memory: 4872kb
input:
17 0.46 0.50 0.50 0.36 0.43 0.42 0.40 0.51 0.50 0.37 0.50 0.49 0.50 0.52 0.50 0.50 0.50 2 3 4 5 6 67 68 69 73 75 76 82 85 86 87 88 100
output:
0.88453794
result:
ok found '0.8845379', expected '0.8845379', error '0.0000000'
Test #9:
score: 0
Accepted
time: 79ms
memory: 4808kb
input:
17 0.36 0.50 0.50 0.49 0.48 0.50 0.6 0.49 0.50 0.50 0.50 0.50 0.50 0.40 0.50 0.50 0.40 1 2 14 15 17 18 19 86 87 88 92 93 94 95 96 97 100
output:
0.93000000
result:
ok found '0.9300000', expected '0.9300000', error '0.0000000'
Test #10:
score: 0
Accepted
time: 68ms
memory: 4772kb
input:
17 0.45 0.49 0.45 0.49 0.50 0.47 0.51 0.49 0.50 0.49 0.50 0.50 0.48 0.50 0.50 0.47 0.50 16 17 26 27 29 30 31 32 33 35 36 87 92 93 94 95 100
output:
0.84543307
result:
ok found '0.8454331', expected '0.8454331', error '0.0000000'
Test #11:
score: 0
Accepted
time: 78ms
memory: 4776kb
input:
17 0.63 0.50 0.36 0.49 0.49 0.50 0.50 0.50 0.50 0.30 0.50 0.50 0.52 0.43 0.50 0.52 0.50 1 5 6 7 8 9 69 70 82 84 85 89 90 92 93 94 100
output:
0.99719192
result:
ok found '0.9971919', expected '0.9971919', error '0.0000000'
Test #12:
score: 0
Accepted
time: 83ms
memory: 4760kb
input:
17 0.50 0.48 0.50 0.50 0.39 0.50 0.50 0.45 0.49 0.47 0.50 0.49 0.50 0.41 0.27 0.50 0.50 52 53 55 56 75 84 85 86 88 89 92 93 94 95 96 98 100
output:
0.16977252
result:
ok found '0.1697725', expected '0.1697725', error '0.0000000'
Test #13:
score: 0
Accepted
time: 79ms
memory: 4796kb
input:
17 0.40 0.49 0.45 0.50 0.50 0.50 0.44 0.34 0.50 0.49 0.50 0.49 0.48 0.48 0.50 0.50 0.50 9 11 12 68 72 87 88 89 90 92 94 95 96 97 98 99 100
output:
0.28270456
result:
ok found '0.2827046', expected '0.2827046', error '0.0000000'
Test #14:
score: 0
Accepted
time: 82ms
memory: 4764kb
input:
17 0.50 0.50 0.50 0.50 0.43 0.50 0.50 0.50 0.46 0.50 0.50 0.45 0.50 0.50 0.50 0.49 0.51 3 4 8 13 14 73 83 84 85 86 87 88 90 92 93 94 100
output:
0.81378907
result:
ok found '0.8137891', expected '0.8137891', error '0.0000000'
Test #15:
score: 0
Accepted
time: 63ms
memory: 4776kb
input:
17 0.48 0.50 0.50 0.50 0.50 0.38 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.48 0.50 0.50 5 7 8 9 10 11 14 15 28 29 87 89 90 91 96 97 100
output:
0.47815639
result:
ok found '0.4781564', expected '0.4781564', error '0.0000000'
Test #16:
score: 0
Accepted
time: 80ms
memory: 4748kb
input:
17 0.50 0.50 0.49 0.50 0.47 0.48 0.46 0.50 0.35 0.50 0.50 0.54 0.50 0.36 0.49 0.50 0.51 3 4 18 20 21 22 23 80 87 88 90 91 93 96 98 99 100
output:
0.93467466
result:
ok found '0.9346747', expected '0.9346747', error '0.0000000'
Test #17:
score: 0
Accepted
time: 62ms
memory: 4796kb
input:
17 0.50 0.49 0.33 0.50 0.49 0.50 0.50 0.45 0.50 0.49 0.49 0.94 0.50 0.50 0.50 0.50 0.49 1 2 8 23 25 26 27 28 29 33 34 38 39 95 96 99 100
output:
0.99486333
result:
ok found '0.9948633', expected '0.9948633', error '0.0000000'
Test #18:
score: 0
Accepted
time: 65ms
memory: 4764kb
input:
17 0.50 0.50 0.34 0.50 0.51 0.50 0.48 0.50 0.50 0.48 0.50 0.50 0.50 0.51 0.49 0.50 0.47 2 3 4 5 6 9 11 12 13 76 79 80 81 92 98 99 100
output:
0.90985193
result:
ok found '0.9098519', expected '0.9098519', error '0.0000000'
Test #19:
score: 0
Accepted
time: 63ms
memory: 4800kb
input:
17 0.50 0.50 0.50 0.49 0.46 0.47 0.39 0.48 0.47 0.50 0.49 0.50 0.49 0.48 0.49 0.52 0.41 1 15 16 17 19 20 29 30 31 37 38 39 40 41 43 45 100
output:
0.99112404
result:
ok found '0.9911240', expected '0.9911240', error '0.0000000'
Test #20:
score: 0
Accepted
time: 82ms
memory: 4728kb
input:
17 0.50 0.50 0.50 0.50 0.50 0.50 0.49 0.44 0.50 0.48 0.50 0.50 0.49 0.50 0.50 0.35 0.50 5 6 8 12 13 14 75 76 79 80 81 83 95 96 98 99 100
output:
0.46804049
result:
ok found '0.4680405', expected '0.4680405', error '0.0000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
9 0.50 0.49 0.50 0.53 0.50 0.50 0.49 0.50 0.43 3 4 5 6 11 13 14 15 46
output:
0.98661776
result:
ok found '0.9866178', expected '0.9866178', error '0.0000000'
Test #22:
score: 0
Accepted
time: 3ms
memory: 3808kb
input:
8 0.67 0.50 0.41 0.37 0.39 0.50 0.40 0.57 1 2 47 50 61 62 64 65
output:
0.98756065
result:
ok found '0.9875607', expected '0.9875606', error '0.0000000'
Test #23:
score: 0
Accepted
time: 3ms
memory: 3796kb
input:
4 0.50 0.49 0.49 0.50 1 8 10 47
output:
0.49216498
result:
ok found '0.4921650', expected '0.4921650', error '0.0000000'
Test #24:
score: 0
Accepted
time: 3ms
memory: 3800kb
input:
7 0.47 0.21 0.49 0.48 0.52 0.50 0.50 1 7 8 29 31 32 34
output:
0.78586486
result:
ok found '0.7858649', expected '0.7858649', error '0.0000000'
Test #25:
score: 0
Accepted
time: 5ms
memory: 3964kb
input:
13 0.50 0.49 0.55 0.50 0.50 0.50 0.50 0.49 0.50 0.49 0.49 0.16 0.47 1 2 3 4 23 24 25 26 32 34 35 36 37
output:
0.78792526
result:
ok found '0.7879253', expected '0.7879253', error '0.0000000'
Test #26:
score: 0
Accepted
time: 3ms
memory: 3756kb
input:
6 0.50 0.50 0.48 0.46 0.50 0.50 1 11 12 13 16 97
output:
0.49490702
result:
ok found '0.4949070', expected '0.4949070', error '0.0000000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
5 0.50 0.38 0.50 0.50 0.46 44 51 52 53 56
output:
0.27385220
result:
ok found '0.2738522', expected '0.2738522', error '0.0000000'
Test #28:
score: 0
Accepted
time: 16ms
memory: 4036kb
input:
15 0.48 0.49 0.50 0.50 0.48 0.48 0.43 0.50 0.50 0.50 0.49 0.50 0.47 0.50 0.47 10 11 13 14 17 19 20 21 22 23 24 25 27 28 29
output:
0.29587158
result:
ok found '0.2958716', expected '0.2958716', error '0.0000000'
Test #29:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
4 0.50 0.44 0.50 0.47 4 5 17 96
output:
0.49003997
result:
ok found '0.4900400', expected '0.4900400', error '0.0000000'
Test #30:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
5 0.50 0.46 0.50 0.50 0.50 13 15 22 24 92
output:
0.47770408
result:
ok found '0.4777041', expected '0.4777041', error '0.0000000'
Test #31:
score: 0
Accepted
time: 3ms
memory: 3744kb
input:
4 0.50 0.50 0.48 0.50 3 9 59 60
output:
0.49701274
result:
ok found '0.4970127', expected '0.4970127', error '0.0000000'
Test #32:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
9 0.43 0.50 0.50 0.50 0.49 0.50 0.50 0.50 0.50 1 2 9 13 48 51 52 54 55
output:
0.49818298
result:
ok found '0.4981830', expected '0.4981830', error '0.0000000'
Test #33:
score: 0
Accepted
time: 3ms
memory: 3720kb
input:
11 0.50 0.43 0.50 0.47 0.50 0.49 0.49 0.46 0.46 0.50 0.50 33 34 35 36 37 38 40 44 45 46 47
output:
0.27064554
result:
ok found '0.2706455', expected '0.2706455', error '0.0000000'
Test #34:
score: 0
Accepted
time: 3ms
memory: 3748kb
input:
5 0.50 0.42 0.43 0.40 0.50 12 14 15 18 96
output:
0.42368074
result:
ok found '0.4236807', expected '0.4236807', error '0.0000000'
Test #35:
score: 0
Accepted
time: 30ms
memory: 4148kb
input:
16 0.49 0.50 0.49 0.42 0.49 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.47 0.36 0.46 11 12 13 14 18 19 20 21 22 23 24 25 26 27 28 29
output:
0.28032827
result:
ok found '0.2803283', expected '0.2803283', error '0.0000000'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
4 0.50 0.42 0.48 0.49 1 2 26 29
output:
0.43961476
result:
ok found '0.4396148', expected '0.4396148', error '0.0000000'
Test #37:
score: 0
Accepted
time: 3ms
memory: 3884kb
input:
14 0.50 0.49 0.40 0.50 0.50 0.48 0.50 0.44 0.50 0.49 0.50 0.50 0.50 0.49 1 6 7 8 15 16 18 20 22 60 63 64 65 66
output:
0.46415891
result:
ok found '0.4641589', expected '0.4641589', error '0.0000000'
Test #38:
score: 0
Accepted
time: 3ms
memory: 3848kb
input:
2 0.50 0.6 46 51
output:
0.95098038
result:
ok found '0.9509804', expected '0.9509804', error '0.0000000'
Test #39:
score: 0
Accepted
time: 1ms
memory: 3908kb
input:
7 0.48 0.49 0.50 0.45 0.50 0.25 0.50 1 8 45 48 50 53 55
output:
0.35417683
result:
ok found '0.3541768', expected '0.3541768', error '0.0000000'
Test #40:
score: 0
Accepted
time: 11ms
memory: 4040kb
input:
15 0.50 0.50 0.49 0.44 0.50 0.38 0.38 0.49 0.50 0.50 0.40 0.49 0.49 0.49 0.50 1 5 10 11 12 13 15 16 17 18 19 20 21 22 45
output:
0.37604282
result:
ok found '0.3760428', expected '0.3760428', error '0.0000000'
Test #41:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
3 0.45 0.5 0.55 98 99 100
output:
0.81500000
result:
ok found '0.8150000', expected '0.8150000', error '0.0000000'
Test #42:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
2 0.75 0.25 1 2
output:
0.75000000
result:
ok found '0.7500000', expected '0.7500000', error '0.0000000'
Test #43:
score: 0
Accepted
time: 84ms
memory: 4800kb
input:
17 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
output:
0.50000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #44:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
4 0.7 0.6 0.4 0.3 2 4 6 8
output:
0.92772210
result:
ok found '0.9277221', expected '0.9277221', error '0.0000000'