QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#826267 | #9778. Brotato | ucup-team3099# | AC ✓ | 376ms | 9724kb | C++23 | 4.0kb | 2024-12-22 05:12:03 | 2024-12-22 05:12:04 |
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, 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