QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#29935#2913. Archery AccuracyGeorge_Plover#AC ✓84ms4872kbC++231.9kb2022-04-23 14:48:012022-04-28 16:03:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-28 16:03:39]
  • 评测
  • 测评结果:AC
  • 用时:84ms
  • 内存:4872kb
  • [2022-04-23 14:48:01]
  • 提交

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'