QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#171375#2913. Archery AccuracyyinshaziyueWA 0ms3904kbC++171.8kb2023-09-09 16:53:172023-09-09 16:55:23

Judging History

你现在查看的是最新测评结果

  • [2023-09-09 16:55:23]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3904kb
  • [2023-09-09 16:53:17]
  • 提交

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'