QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#451279 | #8774. Manhattan Walk | henryx# | AC ✓ | 8ms | 11128kb | C++17 | 2.1kb | 2024-06-23 02:29:49 | 2024-06-23 02:29:49 |
Judging History
answer
#include <bits/stdc++.h>
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define int ll
#define ln '\n'
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define repb(i, a, b) for(int i = (a); i >= (b); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
//#define pb push_back
#define f first
#define s second
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef long double ld;
const int S = int(2e7)+10;
const ll INF = ll(1e18)+10;
const double EPS = 1e-8;
const double PI = 3.141592653589793238;
const int magic = 330LL;
int MOD = int(1e9)+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
template <typename T> void print(T &v) { cout << sz(v) << endl; trav(x, v) cerr << x << " "; cerr << endl; }
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
void solve() {
int n, m, p;
cin >> n >> m >> p;
n++; m++;
vector<vd> f(n, vd(m,0));
rep(i, 1, n)
f[i][1] = (i-1)/4.0;
rep(i, 1, m)
f[1][i] = (i-1)/4.0;
rep(i, 2, n)
rep(j, 2, m) {
double a = min(f[i-1][j], f[i][j-1]), b = max(f[i-1][j], f[i][j-1]);
f[i][j] = 0.5*a + 0.5*(b-a >= 1 ? a+0.5 : (b-a)*((a+b)/2) + (1-b+a)*b);
}
cout << fixed << setprecision(10);
cout << f[n-1][m-1]*p << endl;
}
int32_t main(){
fastio;
#ifdef LOCAL
freopen("stuff.in", "r", stdin);
#endif
int t=1;
// cin >> t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
input:
2 3 8
output:
2.8750000000
result:
ok found '2.8750000', expected '2.8750000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
5 5 5
output:
2.4322338689
result:
ok found '2.4322339', expected '2.4322339', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
1 1 1
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 8ms
memory: 11128kb
input:
1000 1000 1000000000
output:
1782317138.8083746433
result:
ok found '1782317138.8083746', expected '1782317138.8083761', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
1 4 5
output:
3.7500000000
result:
ok found '3.7500000', expected '3.7500000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
4 1 5
output:
3.7500000000
result:
ok found '3.7500000', expected '3.7500000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
1 1 1000000000
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
1 2 1000000000
output:
250000000.0000000000
result:
ok found '250000000.0000000', expected '250000000.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
2 1 1000000000
output:
250000000.0000000000
result:
ok found '250000000.0000000', expected '250000000.0000000', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
1 2 1
output:
0.2500000000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
2 1 1
output:
0.2500000000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
1 10 3
output:
6.7500000000
result:
ok found '6.7500000', expected '6.7500000', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
10 1 3
output:
6.7500000000
result:
ok found '6.7500000', expected '6.7500000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 7ms
memory: 11012kb
input:
997 993 998244353
output:
1779941051.3461623192
result:
ok found '1779941051.3461623', expected '1779941051.3461628', error '0.0000000'
Test #15:
score: 0
Accepted
time: 4ms
memory: 5908kb
input:
988 313 886183312
output:
78753022570.4833374023
result:
ok found '78753022570.4833374', expected '78753022570.4833527', error '0.0000000'
Test #16:
score: 0
Accepted
time: 2ms
memory: 4416kb
input:
583 286 322190846
output:
8636356976.8437118530
result:
ok found '8636356976.8437119', expected '8636356976.8437138', error '0.0000000'
Test #17:
score: 0
Accepted
time: 5ms
memory: 6532kb
input:
892 468 494964816
output:
17125998682.7292461395
result:
ok found '17125998682.7292461', expected '17125998682.7292328', error '0.0000000'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
26 882 386682745
output:
78231677700.7504577637
result:
ok found '78231677700.7504578', expected '78231677700.7504883', error '0.0000000'
Test #19:
score: 0
Accepted
time: 4ms
memory: 9348kb
input:
867 926 422131798
output:
945100500.3991076946
result:
ok found '945100500.3991077', expected '945100500.3991071', error '0.0000000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
37 68 19
output:
62.2844598802
result:
ok found '62.2844599', expected '62.2844599', error '0.0000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
23 90 80
output:
860.0506987358
result:
ok found '860.0506987', expected '860.0506987', error '0.0000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
43 55 85
output:
118.3892679676
result:
ok found '118.3892680', expected '118.3892680', error '0.0000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
93 66 43
output:
97.9048408588
result:
ok found '97.9048409', expected '97.9048409', error '0.0000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 4052kb
input:
78 93 30
output:
44.8454523265
result:
ok found '44.8454523', expected '44.8454523', error '0.0000000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
9 5 481032867
output:
400507342.3667383790
result:
ok found '400507342.3667384', expected '400507342.3667384', error '0.0000000'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
366 73 3
output:
149.4864642331
result:
ok found '149.4864642', expected '149.4864642', error '0.0000000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
6 4 5
output:
2.8946451697
result:
ok found '2.8946452', expected '2.8946452', error '0.0000000'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
8 10 5
output:
3.3973608525
result:
ok found '3.3973609', expected '3.3973609', error '0.0000000'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
10 1 7
output:
15.7500000000
result:
ok found '15.7500000', expected '15.7500000', error '0.0000000'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
10 7 10
output:
7.3716466074
result:
ok found '7.3716466', expected '7.3716466', error '0.0000000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
2 8 1
output:
1.3271069195
result:
ok found '1.3271069', expected '1.3271069', error '0.0000000'