QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#826266 | #9778. Brotato | ucup-team3099# | WA | 119ms | 9716kb | C++23 | 4.0kb | 2024-12-22 05:11:26 | 2024-12-22 05:11:27 |
Judging History
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'