QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#435500 | #8774. Manhattan Walk | ucup-team3691 | TL | 0ms | 3948kb | C++17 | 1.0kb | 2024-06-08 20:21:55 | 2024-06-08 20:21:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n, m;
double p;
double f(int r, int c) {
if(r == n && c == m) return 0;
if(r > n || c > m) return 1e20;
double exp_down = f(r + 1, c);
double exp_right = f(r, c + 1);
double point_down;
if(exp_right + p < exp_down) point_down = exp_right + p * 0.5;
else if(exp_down < exp_right) point_down = exp_down;
else {
double dif = exp_down - exp_right;
assert(exp_right <= exp_down);
assert(dif <= p);
point_down = (dif * exp_right + (p - dif) * exp_down + dif * dif * 0.5) / p;
}
double point_right;
if(exp_down + p < exp_right) point_right = exp_down + p * 0.5;
else if(exp_right < exp_down) point_right = exp_right;
else {
double dif = exp_right - exp_down;
assert(exp_down <= exp_right);
assert(dif <= p);
point_right = (dif * exp_down + (p - dif) * exp_right + dif * dif * 0.5) / p;
}
double exp = 0.5 * (point_down + point_right);
return exp;
}
int main() {
cin >> n >> m >> p;
cout << fixed << setprecision(12) << f(1, 1) << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3948kb
input:
2 3 8
output:
2.875000000000
result:
ok found '2.8750000', expected '2.8750000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
5 5 5
output:
2.432233868874
result:
ok found '2.4322339', expected '2.4322339', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
1 1 1
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: -100
Time Limit Exceeded
input:
1000 1000 1000000000