QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#58545#4228. Double SortxiaoyaowudiWA 4ms13160kbC++17842b2022-10-26 20:23:002022-10-26 20:23:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-26 20:23:02]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:13160kb
  • [2022-10-26 20:23:00]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <iomanip>
constexpr int M=10010,N=60;
typedef long double lf;
lf comb[M][N];
int main(){
	comb[0][0]=1;
	for(int i=1;i<M;++i)
	{
		comb[i][0]=1;
		for(int j=1;j<=i && j<N;++j) comb[i][j]=comb[i-1][j]+comb[i-1][j-1];
	}
	int n,m;
	std::cin>>n>>m;
	lf tot=comb[m][n];
	static lf ans[N];
	for(int i=1;i<=n;++i)
	{
		static lf G[N];
		for(int k=i;k<=n;++k)
		{
			lf cur=1;
			for(int j=i;j<k;++j) cur-=comb[k][j]*G[j];
			G[k]=cur;
		}
		for(int j=1;i*j+n-i<=m;++j)
		{
			lf cur=0;
			for(int k=i;k<=n;++k)
			{
				int sum=m-k*(j-1);
				if(sum>0) cur+=G[k]*comb[n][k]*comb[sum][n];
			}
			ans[n-i+1]+=cur/tot;
		}
	}
	std::cout<<std::setprecision(8);
	for(int i=1;i<=n;++i) ans[i]+=ans[i-1],std::cout<<ans[i]<<" ";
	std::cout<<std::endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 13120kb

input:

3 5

output:

1 2.3 4.5 

result:

ok 3 numbers

Test #2:

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

input:

5 17

output:

1.1313833 2.748384 5.1830963 8.8556884 15 

result:

ok 5 numbers

Test #3:

score: -100
Wrong Answer
time: 4ms
memory: 13160kb

input:

50 10000

output:

4.4328164 12.836597 25.315269 41.955611 62.848076 88.087155 117.77163 152.00489 190.89524 234.55626 283.10722 336.67351 395.3871 459.38706 528.82044 603.84157 684.61522 771.29659 864.07781 963.28363 1069.1995 1182.8876 1300.4125 1432.0691 1531.9654 1700.9226 1619.1745 1400.1379 1447.64 3206.768 2485...

result:

wrong answer 16th numbers differ - expected: '603.8421778', found: '603.8415700', error = '0.0000010'