QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#826267#9778. Brotatoucup-team3099#AC ✓376ms9724kbC++234.0kb2024-12-22 05:12:032024-12-22 05:12:04

Judging History

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

  • [2024-12-22 05:12:04]
  • 评测
  • 测评结果:AC
  • 用时:376ms
  • 内存:9724kb
  • [2024-12-22 05:12:03]
  • 提交

answer

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>
#include <iomanip>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
    int n, k;
    long double p;
    std::cin >> n >> k >> p;
    std::vector<long double> prv(n+1, 1e18), pref(n+1, 0);
    for(int i = 1; i <= n; i++) {
        // target = 1 + p * (pref[i-1] + target)
        // target * (1 - p) = 1 + p * pref[i-1]
        // target = (1 + p * pref[i-1]) / (1 - p)
        pref[i] = (1 + p * pref[i-1]) / (1 - p) + pref[i-1];
    }
    std::cout << std::fixed << std::setprecision(20);
    for(int rep = 0; rep <= std::min(k, 400); rep++) {
        std::vector<long double> suf(n+1, 0);
        for(int i = n-1; i >= 0; i--) {
            // suf[i] = 1 + p * prv[i] + (1 - p) * suf[i+1]
            suf[i] = 1 + p * prv[i] + (1 - p) * suf[i+1];
        }
        int best = -1;
        long double wtf = 1e100;
        for(int i = 0; i <= n; i++) if(pref[i] + suf[i] < wtf) {
            wtf = pref[i] + suf[i];
            best = i;
        }
        //std::cout << "best is " << best << " with " << wtf << '\n';
        std::vector<long double> dp(n+1, 0);
        for(int i = n-1; i >= 0; i--) {
            if(i >= best) {
                dp[i] = suf[i];
            } else {
                // dp[i] = 1 + p * (pref[i] + dp[i]) + (1 - p) * dp[i+1]
                // dp[i] * (1 - p) = 1 + p * pref[i] + (1 - p) * dp[i+1]
                dp[i] = (1 + p * pref[i] + (1 - p) * dp[i+1]) / (1 - p);
            }
            //std::cout << "ans for " << i << " is " << dp[i] << '\n';
        }
        //std::cout << "after " << rep << " got " << dp[0] << '\n';
        prv = dp;
    }
    std::cout << prv[0] << '\n';
}

/*
NEVER FORGET TO:
    Look at the problem's constraints before coding.
How to cheese cf:
    Find a lower bound or upper bound for the problem. Have faith that it is the answer of the problem.
    If it isn't the answer, have more faith or change to another bound god by looking for a better bound.

    Trust guesses. Who has time to think? If people in div2 AC the problem it requires no proof since people don't prove things.

    You must draw cases. Thinking gets you nowhere, so draw cases and reach illogical conclusions from them.
    Sometimes drawing cases is bad because it takes too much time. Faster is to not think at all and just code a bruteforce solution.
    This is called "law of small numbers". If something works for small numbers, surely it works for big numbers.
    https://en.wikipedia.org/wiki/Faulty_generalization#Hasty_generalization don't mind the "faulty" part of it, in competitive programming mistakes are lightly punished
    Don't think about them being right or not, cf is a battle of intuition only.

    Be as stupid as possible in implementation. Trying to be smart is an easy way to get WA.

    Think about 2x2 cases for matrix problems and hope that everything works for the general case.

    Find a necessary condition and trust it to be sufficient. They're basically the same thing.

    Heuristics might speed up your code. Forget about complexity, it's only about ACing and not proving that your solution is good.

    For paths in a grid starting at (1, i) or something like that, assume that they never cross and do D&C

    Consider doing problems in reverse order of queries/updates

    For combinatorics problems, consider symmetry

    For problems that are similar to past problems, think about the differences betweem it and the current problem.
    Sometimes the difference makes no difference. Sometimes it does.

General strategy (MUST DO):
    Try to solve the problem with more restricted constraints.

About testing:
    Test n=1, a[i]=1, a[i]=n, etc. Basically, test low values. No need to test if pretests are strong, but if you get WA it's good.

This isn't a joke. Do it if you get stuck. It's shit practice in my opinion, but do it if you want AC.
*/

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3952kb

input:

5 0
0.5

output:

62.00000000000000000000

result:

ok found '62.000000000', expected '62.000000000', error '0.000000000'

Test #2:

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

input:

5 1
0.5

output:

47.00000000000000000000

result:

ok found '47.000000000', expected '47.000000000', error '0.000000000'

Test #3:

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

input:

10000 0
0.002

output:

247489700298.25371292233467102051

result:

ok found '247489700298.253723145', expected '247489700298.253692627', error '0.000000000'

Test #4:

score: 0
Accepted
time: 14ms
memory: 9664kb

input:

100000 10
0.0002

output:

38767507133.23228795826435089111

result:

ok found '38767507133.232284546', expected '38767507133.232215881', error '0.000000000'

Test #5:

score: 0
Accepted
time: 5ms
memory: 9672kb

input:

100000 0
0.0002

output:

2430683127170.38088059425354003906

result:

ok found '2430683127170.380859375', expected '2430683127170.376953125', error '0.000000000'

Test #6:

score: 0
Accepted
time: 28ms
memory: 9640kb

input:

100000 20
0.0002

output:

801073272.23168243281543254852

result:

ok found '801073272.231682420', expected '801073272.231680870', error '0.000000000'

Test #7:

score: 0
Accepted
time: 63ms
memory: 9664kb

input:

100000 40
0.0002

output:

478148.71842630765291914940

result:

ok found '478148.718426308', expected '478148.718426307', error '0.000000000'

Test #8:

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

input:

99995 4
0.0001

output:

38976542.86817586919642053545

result:

ok found '38976542.868175872', expected '38976542.868175834', error '0.000000000'

Test #9:

score: 0
Accepted
time: 18ms
memory: 9592kb

input:

99995 10
0.0001

output:

3549184.59771202042134063959

result:

ok found '3549184.597712020', expected '3549184.597712017', error '0.000000000'

Test #10:

score: 0
Accepted
time: 34ms
memory: 9628kb

input:

99995 16
0.0001

output:

399507.47055674227547683586

result:

ok found '399507.470556742', expected '399507.470556742', error '0.000000000'

Test #11:

score: 0
Accepted
time: 19ms
memory: 9660kb

input:

99990 8
0.0001

output:

7773463.94793072823495094781

result:

ok found '7773463.947930728', expected '7773463.947930722', error '0.000000000'

Test #12:

score: 0
Accepted
time: 19ms
memory: 9632kb

input:

99990 10
0.0001

output:

3547428.94547230029684214969

result:

ok found '3547428.945472301', expected '3547428.945472297', error '0.000000000'

Test #13:

score: 0
Accepted
time: 22ms
memory: 9624kb

input:

99990 12
0.0001

output:

1647102.02043439692749871028

result:

ok found '1647102.020434397', expected '1647102.020434395', error '0.000000000'

Test #14:

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

input:

16664 1
0.0012

output:

257920044630.86053189635276794434

result:

ok found '257920044630.860534668', expected '257920044630.860534668', error '0.000000000'

Test #15:

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

input:

16664 21
0.0012

output:

92190688.54441501431574579328

result:

ok found '92190688.544415012', expected '92190688.544415027', error '0.000000000'

Test #16:

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

input:

16664 41
0.0012

output:

59865.09178591990928808286

result:

ok found '59865.091785920', expected '59865.091785920', error '0.000000000'

Test #17:

score: 0
Accepted
time: 3ms
memory: 4356kb

input:

16659 5
0.0003

output:

63366.26440695477444009498

result:

ok found '63366.264406955', expected '63366.264406955', error '0.000000000'

Test #18:

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

input:

16659 11
0.0003

output:

18120.91186354253214041421

result:

ok found '18120.911863543', expected '18120.911863543', error '0.000000000'

Test #19:

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

input:

16659 17
0.0003

output:

16666.55545196740557578607

result:

ok found '16666.555451967', expected '16666.555451967', error '0.000000000'

Test #20:

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

input:

16654 9
0.0001

output:

16656.07941657562629522715

result:

ok found '16656.079416576', expected '16656.079416576', error '0.000000000'

Test #21:

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

input:

16654 11
0.0001

output:

16655.67412217240140215324

result:

ok found '16655.674122172', expected '16655.674122172', error '0.000000000'

Test #22:

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

input:

16654 13
0.0001

output:

16655.66569536266710827022

result:

ok found '16655.665695363', expected '16655.665695363', error '0.000000000'

Test #23:

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

input:

2774 2
0.0072

output:

28951389306.98751270584762096405

result:

ok found '28951389306.987514496', expected '28951389306.987514496', error '0.000000000'

Test #24:

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

input:

2774 22
0.0072

output:

11312241.45065394159246352501

result:

ok found '11312241.450653942', expected '11312241.450653942', error '0.000000000'

Test #25:

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

input:

2774 42
0.0072

output:

8222.41510850861823378466

result:

ok found '8222.415108509', expected '8222.415108509', error '0.000000000'

Test #26:

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

input:

2769 6
0.0021

output:

13600.58235573161154885469

result:

ok found '13600.582355732', expected '13600.582355732', error '0.000000000'

Test #27:

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

input:

2769 12
0.0021

output:

3239.54997821112632849783

result:

ok found '3239.549978211', expected '3239.549978211', error '0.000000000'

Test #28:

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

input:

2769 18
0.0021

output:

2776.62819487524041561777

result:

ok found '2776.628194875', expected '2776.628194875', error '0.000000000'

Test #29:

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

input:

2764 10
0.0007

output:

2765.98707395508637918446

result:

ok found '2765.987073955', expected '2765.987073955', error '0.000000000'

Test #30:

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

input:

2764 12
0.0007

output:

2765.93736284997197527602

result:

ok found '2765.937362850', expected '2765.937362850', error '0.000000000'

Test #31:

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

input:

2764 14
0.0007

output:

2765.93617670347270620645

result:

ok found '2765.936176703', expected '2765.936176704', error '0.000000000'

Test #32:

score: 0
Accepted
time: 376ms
memory: 9716kb

input:

100000 1000000000
0.0001

output:

100010.00100010005359507659

result:

ok found '100010.001000100', expected '100010.001000100', error '0.000000000'

Test #33:

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

input:

1 1000000000
0.5

output:

2.00000000000000000000

result:

ok found '2.000000000', expected '2.000000000', error '0.000000000'

Test #34:

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

input:

50 50
0.25

output:

66.73418733370452768372

result:

ok found '66.734187334', expected '66.734187334', error '0.000000000'

Test #35:

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

input:

40 100
0.5

output:

788.63312396627232125912

result:

ok found '788.633123966', expected '788.633123966', error '0.000000000'

Test #36:

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

input:

40 160
0.5

output:

80.00000025524792005016

result:

ok found '80.000000255', expected '80.000000255', error '0.000000000'

Test #37:

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

input:

40 162
0.5

output:

80.00000009823374218232

result:

ok found '80.000000098', expected '80.000000098', error '0.000000000'

Test #38:

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

input:

40 1000000000
0.5

output:

80.00000000000000000000

result:

ok found '80.000000000', expected '80.000000000', error '0.000000000'

Test #39:

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

input:

40 0
0.5000

output:

2199023255550.00000000000000000000

result:

ok found '2199023255550.000000000', expected '2199023255550.000000000', error '0.000000000'

Test #40:

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

input:

40 1
0.5000

output:

1649267441663.00000000000000000000

result:

ok found '1649267441663.000000000', expected '1649267441663.000000000', error '0.000000000'

Test #41:

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

input:

40 2
0.5000

output:

1236950581248.25000000000000000000

result:

ok found '1236950581248.250000000', expected '1236950581248.250000000', error '0.000000000'

Test #42:

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

input:

40 3
0.5000

output:

962072674305.00000000000000000000

result:

ok found '962072674305.000000000', expected '962072674305.000000000', error '0.000000000'

Test #43:

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

input:

40 4
0.5000

output:

738734374914.21875000000000000000

result:

ok found '738734374914.218750000', expected '738734374914.218750000', error '0.000000000'

Test #44:

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

input:

40 5
0.5000

output:

575525617666.95312500000000000000

result:

ok found '575525617666.953125000', expected '575525617666.953125000', error '0.000000000'

Test #45:

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

input:

40 10
0.5000

output:

173409304583.13256835937500000000

result:

ok found '173409304583.132568359', expected '173409304583.132568359', error '0.000000000'

Test #46:

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

input:

40 15
0.5000

output:

55390502923.07350826263427734375

result:

ok found '55390502923.073509216', expected '55390502923.073509216', error '0.000000000'

Test #47:

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

input:

40 20
0.5000

output:

18180087821.74740450084209442139

result:

ok found '18180087821.747406006', expected '18180087821.747406006', error '0.000000000'

Test #48:

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

input:

40 25
0.5000

output:

5963269457.31878360174596309662

result:

ok found '5963269457.318783760', expected '5963269457.318783760', error '0.000000000'

Test #49:

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

input:

40 30
0.5000

output:

2008652291.20979898096993565559

result:

ok found '2008652291.209799051', expected '2008652291.209799051', error '0.000000000'

Test #50:

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

input:

40 35
0.5000

output:

676323760.76680406328523531556

result:

ok found '676323760.766804099', expected '676323760.766804099', error '0.000000000'

Test #51:

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

input:

40 40
0.5000

output:

231036317.11780157298198901117

result:

ok found '231036317.117801577', expected '231036317.117801577', error '0.000000000'

Test #52:

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

input:

40 45
0.5000

output:

79224360.24568989693943876773

result:

ok found '79224360.245689899', expected '79224360.245689899', error '0.000000000'

Test #53:

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

input:

40 50
0.5000

output:

27134304.85083361087890807539

result:

ok found '27134304.850833610', expected '27134304.850833610', error '0.000000000'

Test #54:

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

input:

2 1
0.0001

output:

2.00020003000400050015

result:

ok found '2.000200030', expected '2.000200030', error '0.000000000'

Test #55:

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

input:

2 0
0.0001

output:

2.00030004000500060009

result:

ok found '2.000300040', expected '2.000300040', error '0.000000000'

Test #56:

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

input:

2 2
0.0001

output:

2.00020002000300040025

result:

ok found '2.000200020', expected '2.000200020', error '0.000000000'

Test #57:

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

input:

2 3
0.0001

output:

2.00020002000200030007

result:

ok found '2.000200020', expected '2.000200020', error '0.000000000'

Test #58:

score: 0
Accepted
time: 82ms
memory: 9708kb

input:

100000 60
0.0002

output:

100020.27483830504989015253

result:

ok found '100020.274838305', expected '100020.274838305', error '0.000000000'

Test #59:

score: 0
Accepted
time: 95ms
memory: 9656kb

input:

100000 80
0.0002

output:

100020.00400080025092108826

result:

ok found '100020.004000800', expected '100020.004000800', error '0.000000000'

Test #60:

score: 0
Accepted
time: 99ms
memory: 9592kb

input:

100000 100
0.0002

output:

100020.00400080024836313441

result:

ok found '100020.004000800', expected '100020.004000800', error '0.000000000'

Test #61:

score: 0
Accepted
time: 108ms
memory: 9660kb

input:

100000 120
0.0002

output:

100020.00400080024836313441

result:

ok found '100020.004000800', expected '100020.004000800', error '0.000000000'

Test #62:

score: 0
Accepted
time: 139ms
memory: 9724kb

input:

100000 140
0.0002

output:

100020.00400080024836313441

result:

ok found '100020.004000800', expected '100020.004000800', error '0.000000000'

Test #63:

score: 0
Accepted
time: 173ms
memory: 9680kb

input:

100000 180
0.0002

output:

100020.00400080024836313441

result:

ok found '100020.004000800', expected '100020.004000800', error '0.000000000'

Test #64:

score: 0
Accepted
time: 48ms
memory: 9596kb

input:

100000 55
0.0002

output:

100070.85032820329931979586

result:

ok found '100070.850328203', expected '100070.850328203', error '0.000000000'

Test #65:

score: 0
Accepted
time: 67ms
memory: 9724kb

input:

100000 50
0.0002

output:

103207.68419309129157568350

result:

ok found '103207.684193091', expected '103207.684193091', error '0.000000000'

Extra Test:

score: 0
Extra Test Passed