QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#171375 | #2913. Archery Accuracy | yinshaziyue | WA | 0ms | 3904kb | C++17 | 1.8kb | 2023-09-09 16:53:17 | 2023-09-09 16:55:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n, s[17];
double p[17], dp[80000];
struct matrix {
double a[2][2];
matrix operator*(const matrix& rhs) const {
matrix ret;
for (int i = 0; i <= 1; ++i) {
for (int j = 0; j <= 1; ++j) {
ret.a[i][j] = 0;
for (int k = 0; i <= 1; ++k) {
ret.a[i][j] += a[i][k] * rhs.a[k][j];
}
}
}
return ret;
}
matrix operator^(const int& k) const {
matrix m = *this,ret;
for (int i = 0; i <= 1; ++i) {
for (int j = 0; j <= 1; ++j) {
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,mn,ma;
m.a[0][0] = 0, m.a[0][1] = 1;
m.a[1][0] = 1 - 1 / p, m.a[1][1] = 1 / p;
mn = m ^ (a + b);
double x = 1 / mn.a[0][1];
ma = m ^ a;
double ret = ma.a[0][1] * x;
return ret;
}
int main() {
cin >> n;
for (int i = 0; i <= n - 1; ++i) {
cin >> p[i];
}
s[0] = 0;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
}
dp[0] = 1;
for (int S = 1; S <= (1 << n) - 1; ++S) {
int t = __builtin_popcount(S);
dp[S] = 0;
for (int i = 0; i <= n - 1; ++i) {
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]));
}
}
}
cout << fixed << setprecision(7) << dp[(1 << n) - 1] << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3904kb
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.0000000
result:
wrong answer 1st numbers differ - expected: '0.4516422', found: '0.0000000', error = '0.4516422'