QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#826266#9778. Brotatoucup-team3099#WA 119ms9716kbC++234.0kb2024-12-22 05:11:262024-12-22 05:11:27

Judging History

This is the latest submission verdict.

  • [2024-12-22 05:11:27]
  • Judged
  • Verdict: WA
  • Time: 119ms
  • Memory: 9716kb
  • [2024-12-22 05:11:26]
  • Submitted

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, 100); 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.
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3848kb

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: 1ms
memory: 4020kb

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: 16ms
memory: 9708kb

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: 9596kb

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: 45ms
memory: 9716kb

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: 3ms
memory: 9700kb

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: 7ms
memory: 9640kb

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: 31ms
memory: 9612kb

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: 15ms
memory: 9596kb

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: 23ms
memory: 9608kb

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: 20ms
memory: 9712kb

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: 4296kb

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: 0ms
memory: 4400kb

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: 6ms
memory: 4352kb

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: 0ms
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: 4472kb

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: 0ms
memory: 4464kb

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: 4368kb

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: 4ms
memory: 4384kb

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: 0ms
memory: 4376kb

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: 4084kb

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: 1ms
memory: 3988kb

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: 2ms
memory: 4020kb

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: 4140kb

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: 3984kb

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: 3972kb

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: 4080kb

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: 4080kb

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: 3976kb

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: 119ms
memory: 9600kb

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: 3728kb

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: 3864kb

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: 0ms
memory: 3848kb

input:

40 100
0.5

output:

788.63312396627232125912

result:

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

Test #36:

score: -100
Wrong Answer
time: 0ms
memory: 3800kb

input:

40 160
0.5

output:

788.63312396627232125912

result:

wrong answer 1st numbers differ - expected: '80.0000003', found: '788.6331240', error = '8.8579140'