QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#643883#8774. Manhattan Walkainta#AC ✓14ms11788kbC++203.9kb2024-10-16 05:19:592024-10-16 05:20:00

Judging History

你现在查看的是最新测评结果

  • [2024-10-16 05:20:00]
  • 评测
  • 测评结果:AC
  • 用时:14ms
  • 内存:11788kb
  • [2024-10-16 05:19:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}


struct modinfo{uint mod,root;};
template<modinfo const&ref>
struct modular{
	static constexpr uint const &mod=ref.mod;
	static modular root(){return modular(ref.root);}
	uint v;
	//modular(initializer_list<uint>ls):v(*ls.bg){}
	modular(ll vv=0){s(vv%mod+mod);}
	modular& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	modular operator-()const{return modular()-*this;}
	modular& operator+=(const modular&rhs){return s(v+rhs.v);}
	modular&operator-=(const modular&rhs){return s(v+mod-rhs.v);}
	modular&operator*=(const modular&rhs){
		v=ull(v)*rhs.v%mod;
		return *this;
	}
	modular&operator/=(const modular&rhs){return *this*=rhs.inv();}
	modular operator+(const modular&rhs)const{return modular(*this)+=rhs;}
	modular operator-(const modular&rhs)const{return modular(*this)-=rhs;}
	modular operator*(const modular&rhs)const{return modular(*this)*=rhs;}
	modular operator/(const modular&rhs)const{return modular(*this)/=rhs;}
	modular pow(int n)const{
		modular res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modular inv()const{return pow(mod-2);}
	/*modular inv()const{
		int x,y;
		int g=extgcd(v,mod,x,y);
		assert(g==1);
		if(x<0)x+=mod;
		return modular(x);
	}*/
	friend modular operator+(int x,const modular&y){
		return modular(x)+y;
	}
	friend modular operator-(int x,const modular&y){
		return modular(x)-y;
	}
	friend modular operator*(int x,const modular&y){
		return modular(x)*y;
	}
	friend modular operator/(int x,const modular&y){
		return modular(x)/y;
	}
	friend ostream& operator<<(ostream&os,const modular&m){
		return os<<m.v;
	}
	friend istream& operator>>(istream&is,modular&m){
		ll x;is>>x;
		m=modular(x);
		return is;
	}
	bool operator<(const modular&r)const{return v<r.v;}
	bool operator==(const modular&r)const{return v==r.v;}
	bool operator!=(const modular&r)const{return v!=r.v;}
	explicit operator bool()const{
		return v;
	}
};
extern constexpr modinfo base{998244353,0};
using mint=modular<base>;
using pdi = pair<double, int>;
using ld = long double;
#define N_  200010

int n, p, m;
double D[1010][1010];
void Solve(){
	scanf("%d%d%d",&n,&m,&p);
	rng(i,0,n){
		rng(j,0,m){
			if(!i && !j)continue;
			if(i==0){
				D[i][j] = D[i][j-1] + p*0.25;
			}
			else if(j==0){
				D[i][j] = D[i-1][j] + p*0.25;
			}
			else{
				double a = min(D[i-1][j], D[i][j-1]), b= max(D[i-1][j], D[i][j-1]);
				double d = b-a;
				if(d>=p){
					D[i][j] = a+p*0.25;
					continue;
				}
				D[i][j] = b * ((p-d)/(2*p)) + a * 0.5 + (a+d/2) * (d/(2*p)); //   >= d
			//	printf("%d %d %f\n",i,j,D[i][j]);



//from b to a+p,  x* (probability that x-b to p) + (b+x)*0.5*(probability that 0 to x-b)    dx
// x * (p-x+b)/(2*p) + (b+x)*0.5*(x-b)/(2*p)  dx
// 2x(p-x+b) + (b+x)(x-b) dx  /4p

// -x^2 + 2(b+p)x - b^2  dx  / 4p
// -1/3x^3 + (b+p)x^2 - b^2x

			}
		}
	}
	printf("%.10f\n",D[n-1][m-1]);
}

int main(){
	int TC=1;
	//scanf("%d",&TC);
	while(TC--){
		Solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3860kb

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

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

input:

1 1 1

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

score: 0
Accepted
time: 14ms
memory: 11736kb

input:

1000 1000 1000000000

output:

1782317138.8083772659

result:

ok found '1782317138.8083773', expected '1782317138.8083761', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3908kb

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

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

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

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

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

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

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

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

input:

10 1 3

output:

6.7500000000

result:

ok found '6.7500000', expected '6.7500000', error '0.0000000'

Test #14:

score: 0
Accepted
time: 9ms
memory: 11788kb

input:

997 993 998244353

output:

1779941051.3461630344

result:

ok found '1779941051.3461630', expected '1779941051.3461628', error '0.0000000'

Test #15:

score: 0
Accepted
time: 6ms
memory: 11440kb

input:

988 313 886183312

output:

78753022570.4833526611

result:

ok found '78753022570.4833527', expected '78753022570.4833527', error '0.0000000'

Test #16:

score: 0
Accepted
time: 3ms
memory: 9316kb

input:

583 286 322190846

output:

8636356976.8437137604

result:

ok found '8636356976.8437138', expected '8636356976.8437138', error '0.0000000'

Test #17:

score: 0
Accepted
time: 0ms
memory: 11744kb

input:

892 468 494964816

output:

17125998682.7292499542

result:

ok found '17125998682.7292500', expected '17125998682.7292328', error '0.0000000'

Test #18:

score: 0
Accepted
time: 1ms
memory: 4136kb

input:

26 882 386682745

output:

78231677700.7503967285

result:

ok found '78231677700.7503967', expected '78231677700.7504883', error '0.0000000'

Test #19:

score: 0
Accepted
time: 7ms
memory: 10924kb

input:

867 926 422131798

output:

945100500.3991067410

result:

ok found '945100500.3991067', expected '945100500.3991071', error '0.0000000'

Test #20:

score: 0
Accepted
time: 0ms
memory: 4004kb

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

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

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

input:

93 66 43

output:

97.9048408588

result:

ok found '97.9048409', expected '97.9048409', error '0.0000000'

Test #24:

score: 0
Accepted
time: 1ms
memory: 5968kb

input:

78 93 30

output:

44.8454523265

result:

ok found '44.8454523', expected '44.8454523', error '0.0000000'

Test #25:

score: 0
Accepted
time: 1ms
memory: 3940kb

input:

9 5 481032867

output:

400507342.3667382598

result:

ok found '400507342.3667383', expected '400507342.3667384', error '0.0000000'

Test #26:

score: 0
Accepted
time: 1ms
memory: 6828kb

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

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

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

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

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

input:

2 8 1

output:

1.3271069195

result:

ok found '1.3271069', expected '1.3271069', error '0.0000000'