QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387121#4687. Weather Reportsam571128AC ✓13ms4300kbC++201.6kb2024-04-12 04:52:562024-04-12 04:52:56

Judging History

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

  • [2024-04-12 04:52:56]
  • 评测
  • 测评结果:AC
  • 用时:13ms
  • 内存:4300kb
  • [2024-04-12 04:52:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const ld pi = acos(-1);

ll C[21][21];

ll n;

vector<pair<ld, ll>> v;
ld p[4];

void dfs(ll i, ll t, ll ct, ld x) {
    if (i == 4) {
        if (t == n) {
            v.push_back({x, ct});
        }
        return;
    }

    for (ll j = 0; j + t <= n; j++) {
        dfs(i + 1, j + t, ct * C[n - t][j], x);
        x *= p[i];
    }
}

int main() {
    C[0][0] = 1;
    for (ll i = 1; i <= 20; i++) {
        for (ll j = 0; j <= i; j++) {
            C[i][j] = C[i - 1][j];
            if (j > 0) C[i][j] += C[i - 1][j - 1];
        }
    }

    cin >> n;
    for (ll i = 0; i < 4; i++) cin >> p[i];

    dfs(0, 0, 1, 1);

    sort(v.begin(), v.end());
    multiset<pair<ld, ll>> s(v.begin(), v.end());

    ll ct = 1LL << (2 * n);
    ll t = 0;
    // for (auto [x, y]: v) {
    //     cout << x << " " << y << endl;
    // }
    // cout << ct << " " << t << '\n';

    ld ans = 0;
    while (ct > 1) {
        auto [x, c] = *s.begin();
        s.erase(s.begin());
        // cout << x << " " << c << " " << ct << endl;
        if (c >= 2) {
            ans += 2 * x * (c / 2);
            ct -= c / 2;
            s.insert({2 * x, c / 2});
            c %= 2;
        }

        if (c == 1 && ct > 1) {
            assert(s.size());
            auto [y, d] = *s.begin();
            s.erase(s.begin());
            ans += x + y;
            ct--;
            s.insert({x + y, 1});
            --d;
            if (d > 0) s.insert({y, d});
        }
    }
    cout << setprecision(12) << fixed << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3784kb

input:

2
0.9 0.049999 0.05 0.000001

output:

1.457509949996

result:

ok found '1.45751', expected '1.45751', error '0.00000'

Test #2:

score: 0
Accepted
time: 9ms
memory: 4300kb

input:

20
0.25 0.25 0.25 0.25

output:

40.000000000000

result:

ok found '40.00000', expected '40.00000', error '0.00000'

Test #3:

score: 0
Accepted
time: 9ms
memory: 4232kb

input:

19
0.5 0.3 0.08615 0.11385

output:

32.000055102909

result:

ok found '32.00006', expected '32.00006', error '0.00000'

Test #4:

score: 0
Accepted
time: 7ms
memory: 4216kb

input:

19
0.255 0.265 0.235 0.245

output:

37.994344661379

result:

ok found '37.99434', expected '37.99435', error '0.00000'

Test #5:

score: 0
Accepted
time: 11ms
memory: 4100kb

input:

20
0.066667 0.133333 0.266667 0.533333

output:

32.848884802099

result:

ok found '32.84888', expected '32.84889', error '0.00000'

Test #6:

score: 0
Accepted
time: 8ms
memory: 4176kb

input:

20
0.27 0.26 0.24 0.23

output:

39.970024423078

result:

ok found '39.97002', expected '39.97002', error '0.00000'

Test #7:

score: 0
Accepted
time: 9ms
memory: 4124kb

input:

20
0.5 0.2 0.175 0.125

output:

35.617733235788

result:

ok found '35.61773', expected '35.61773', error '0.00000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

2
0.9 0.05 0.049999 0.000001

output:

1.457509949996

result:

ok found '1.45751', expected '1.45751', error '0.00000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

3
0.25 0.25 0.25 0.25

output:

6.000000000000

result:

ok found '6.00000', expected '6.00000', error '0.00000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

9
0.25 0.25 0.25 0.25

output:

18.000000000000

result:

ok found '18.00000', expected '18.00000', error '0.00000'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

9
0.1 0.4 0.3 0.2

output:

16.645985579000

result:

ok found '16.64599', expected '16.64599', error '0.00000'

Test #12:

score: 0
Accepted
time: 12ms
memory: 4276kb

input:

20
0.56 0.1 0.01 0.33

output:

27.926967193580

result:

ok found '27.92697', expected '27.92697', error '0.00000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3996kb

input:

1
0.5 0.25 0.125 0.125

output:

1.750000000000

result:

ok found '1.75000', expected '1.75000', error '0.00000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

2
0.5 0.25 0.125 0.125

output:

3.500000000000

result:

ok found '3.50000', expected '3.50000', error '0.00000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

3
0.5 0.25 0.125 0.125

output:

5.250000000000

result:

ok found '5.25000', expected '5.25000', error '0.00000'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3948kb

input:

11
0.5 0.25 0.125 0.125

output:

19.250000000000

result:

ok found '19.25000', expected '19.25000', error '0.00000'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3964kb

input:

1
0.403 0.199 0.199 0.199

output:

1.995000000000

result:

ok found '1.99500', expected '1.99500', error '0.00000'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

1
0.199 0.403 0.199 0.199

output:

1.995000000000

result:

ok found '1.99500', expected '1.99500', error '0.00000'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

1
0.199 0.199 0.403 0.199

output:

1.995000000000

result:

ok found '1.99500', expected '1.99500', error '0.00000'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3964kb

input:

1
0.199 0.199 0.199 0.403

output:

1.995000000000

result:

ok found '1.99500', expected '1.99500', error '0.00000'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

4
0.4 0.25 0.24 0.11

output:

7.525134570000

result:

ok found '7.52513', expected '7.52513', error '0.00000'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

4
0.25 0.4 0.24 0.11

output:

7.525134570000

result:

ok found '7.52513', expected '7.52513', error '0.00000'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

4
0.25 0.24 0.4 0.11

output:

7.525134570000

result:

ok found '7.52513', expected '7.52513', error '0.00000'

Test #24:

score: 0
Accepted
time: 0ms
memory: 4004kb

input:

4
0.25 0.24 0.11 0.4

output:

7.525134570000

result:

ok found '7.52513', expected '7.52513', error '0.00000'

Test #25:

score: 0
Accepted
time: 0ms
memory: 4056kb

input:

4
0.0001 0.0002 0.00034 0.99936

output:

1.008988515133

result:

ok found '1.00899', expected '1.00899', error '0.00000'

Test #26:

score: 0
Accepted
time: 0ms
memory: 4000kb

input:

4
0.99936 0.00034 0.0002 0.0001

output:

1.008988515133

result:

ok found '1.00899', expected '1.00899', error '0.00000'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

4
0.00034 0.99936 0.0002 0.0001

output:

1.008988515133

result:

ok found '1.00899', expected '1.00899', error '0.00000'

Test #28:

score: 0
Accepted
time: 11ms
memory: 4052kb

input:

20
0.000001 0.999997 0.000001 0.000001

output:

1.000357008384

result:

ok found '1.00036', expected '1.00036', error '0.00000'

Test #29:

score: 0
Accepted
time: 4ms
memory: 3992kb

input:

15
0.000001 0.000001 0.999997 0.000001

output:

1.000252004458

result:

ok found '1.00025', expected '1.00025', error '0.00000'

Test #30:

score: 0
Accepted
time: 8ms
memory: 3992kb

input:

18
0.01 0.345 0.345 0.3

output:

29.675058743432

result:

ok found '29.67506', expected '29.67506', error '0.00000'

Test #31:

score: 0
Accepted
time: 6ms
memory: 4076kb

input:

17
0.13 0.35 0.13 0.39

output:

31.056836158746

result:

ok found '31.05684', expected '31.05684', error '0.00000'

Test #32:

score: 0
Accepted
time: 11ms
memory: 4232kb

input:

20
0.14 0.33 0.14 0.39

output:

37.067096888594

result:

ok found '37.06710', expected '37.06710', error '0.00000'

Test #33:

score: 0
Accepted
time: 13ms
memory: 4072kb

input:

20
0.125001 0.25 0.5 0.124999

output:

35.000000000000

result:

ok found '35.00000', expected '35.00000', error '0.00000'

Test #34:

score: 0
Accepted
time: 12ms
memory: 4056kb

input:

20
0.01 0.34503 0.34503 0.29994

output:

32.967203525345

result:

ok found '32.96720', expected '32.96720', error '0.00000'

Test #35:

score: 0
Accepted
time: 12ms
memory: 4220kb

input:

20
0.4 0.2 0.3 0.1

output:

36.959297167070

result:

ok found '36.95930', expected '36.95930', error '0.00000'

Test #36:

score: 0
Accepted
time: 13ms
memory: 4200kb

input:

20
0.01 0.02 0.03 0.94

output:

8.324709688145

result:

ok found '8.32471', expected '8.32471', error '0.00000'

Test #37:

score: 0
Accepted
time: 11ms
memory: 4128kb

input:

20
0.991 0.003 0.003 0.003

output:

2.121381821746

result:

ok found '2.12138', expected '2.12138', error '0.00000'

Test #38:

score: 0
Accepted
time: 12ms
memory: 4140kb

input:

20
0.495 0.005 0.495 0.005

output:

21.675401364773

result:

ok found '21.67540', expected '21.67540', error '0.00000'

Test #39:

score: 0
Accepted
time: 10ms
memory: 3992kb

input:

20
0.492 0.008 0.493 0.007

output:

22.322928144766

result:

ok found '22.32293', expected '22.32293', error '0.00000'

Test #40:

score: 0
Accepted
time: 11ms
memory: 4168kb

input:

20
0.032 0.051 0.023 0.894

output:

12.985654969506

result:

ok found '12.98565', expected '12.98565', error '0.00000'

Test #41:

score: 0
Accepted
time: 7ms
memory: 3992kb

input:

20
0.002 0.01 0.09 0.898

output:

10.761968792601

result:

ok found '10.76197', expected '10.76197', error '0.00000'

Test #42:

score: 0
Accepted
time: 11ms
memory: 4032kb

input:

20
0.91 0.03 0.03 0.03

output:

11.642446903928

result:

ok found '11.64245', expected '11.64245', error '0.00000'