QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#864829#2430. Gem IslandfryanAC ✓60ms9820kbC++201.1kb2025-01-21 09:42:062025-01-21 09:42:07

Judging History

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

  • [2025-01-21 09:42:07]
  • 评测
  • 测评结果:AC
  • 用时:60ms
  • 内存:9820kb
  • [2025-01-21 09:42:06]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long
#define ld long double

const int mxn = 505;
ld ft[mxn];

ld nck(int a, int b) {
	return ft[a]/ft[b]/ft[a-b];
}

array<ld,2> FF[mxn][mxn];

array<ld,2> f(int n, int d, int r) {
	if (FF[n][d][0]) return FF[n][d];
	//count, ev
//	cout<<n<<" "<<d<<" "<<r<<"\n";
	if (d < 0) {
		return {0,0};
	}
	if (n <= 0) {
		return {0,0};
	}
	if (!d) {
		return {1,0};
	}
	ld cnt = 0, val = 0;
	for (int rem=0; rem<=n; rem++) {
		auto [cc,vv] = f(n-rem,d-n+rem,r);
		if (!cc) continue;
		cnt += nck(n,rem) * cc;
		val += nck(n,rem) * (vv + min(n-rem,r)*cc);
//		if (d==3) {
//			cout<<n-rem<<" "<<d-n+rem<<": "<<nck(n,rem) * cc<<" "<<nck(n,rem) * (vv + min(n-rem,r))<<"\n";
//		}
	}
	
	FF[n][d] = {cnt,val};
	
	return {cnt,val};
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	ft[0] = 1;
	for (int i=1; i<mxn; i++) {
		ft[i] = i*ft[i-1];
	}
	
	int n,d,r; cin>>n>>d>>r;
	auto [a,b] = f(n,d,r);
	ld v = b/a+r;
	cout<<fixed<<setprecision(100)<<v;
	
	
} 

Details

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

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

Test #23:

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

Test #24:

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

Test #25:

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

Test #26:

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

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

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

Test #31:

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

Test #32:

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

Test #33:

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

Test #34:

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

Test #35:

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

Test #36:

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

Test #37:

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

Test #38:

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

Test #39:

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

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

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

Test #44:

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

Test #45:

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

Test #46:

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

Test #47:

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

Test #48:

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

Test #49:

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

Test #50:

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

Test #51:

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

Test #52:

score: 0
Accepted
time: 2ms
memory: 4480kb

Test #53:

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

Test #54:

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

Test #55:

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

Test #56:

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

Test #57:

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

Test #58:

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

Test #59:

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

Test #60:

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

Test #61:

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

Test #62:

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

Test #63:

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

Test #64:

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

Test #65:

score: 0
Accepted
time: 50ms
memory: 7296kb

Test #66:

score: 0
Accepted
time: 11ms
memory: 6016kb

Test #67:

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

Test #68:

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

Test #69:

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

Test #70:

score: 0
Accepted
time: 46ms
memory: 9820kb

Test #71:

score: 0
Accepted
time: 60ms
memory: 8320kb

Test #72:

score: 0
Accepted
time: 59ms
memory: 8448kb

Test #73:

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

Test #74:

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

Test #75:

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

Test #76:

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

Test #77:

score: 0
Accepted
time: 2ms
memory: 4736kb

Test #78:

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

Test #79:

score: 0
Accepted
time: 2ms
memory: 4608kb

Test #80:

score: 0
Accepted
time: 19ms
memory: 6656kb

Test #81:

score: 0
Accepted
time: 58ms
memory: 8576kb

Test #82:

score: 0
Accepted
time: 60ms
memory: 8320kb

Test #83:

score: 0
Accepted
time: 60ms
memory: 8448kb

Test #84:

score: 0
Accepted
time: 60ms
memory: 8448kb