QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#885435#4228. Double SortjryggsTL 1ms6100kbC++141.4kb2025-02-06 15:39:052025-02-06 15:39:05

Judging History

This is the latest submission verdict.

  • [2025-02-06 15:39:05]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 6100kb
  • [2025-02-06 15:39:05]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const int N=55,M=1e4+5;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
int n,m;
long double jie[M],inv[M],f[N][M][2],g[N][M][N][2];
int main(){
	n=read(),m=read();
	jie[0]=inv[0]=1;
	for(int i = 1;i<=n;i++)jie[i]=jie[i-1]*i,inv[i]=inv[i-1]/i;
	f[0][0][1]=jie[n];
	for(int i = 0;i<=n;i++){
		for(int j = i;j<=m;j++){
			if(i&&i+j<=m){
				f[i][i+j][1]=(f[i][i+j][1]+f[i][j][0]+f[i][j][1]);
				for(int k = 1;k<=i;k++)g[i][j+i][k][1]=(g[i][i+j][k][1]+g[i][j][k][0]+f[i][j][0]+g[i][j][k][1]+f[i][j][1]);
			}
			for(int l = 1;l+i<=n;l++){
				f[i+l][j+l][0]=(f[i+l][j+l][0]+f[i][j][1]*inv[l]);
				for(int k = i+1;k<=i+l;k++)g[i+l][j+l][k][0]=(g[i+l][j+l][k][0]+f[i][j][1]*inv[l]);
			}
			for(int k = 1;k<=i;k++){
				for(int l = 1;l+i<=n;l++)g[i+l][j+l][k][0]=(g[i+l][j+l][k][0]+g[i][j][k][1]*inv[l]);
			}
		}
	}
	long double ans=0,val=0;
	for(int i = n;i<=m;i++){
		long double now = 1;
		for(int j = n;j<=i-1;j++)now*=j*1.0/(j-n+1);
		val+=now;
	}
	for(int i = n;i>=1;i--){
		for(int j = n;j<=m;j++){
			ans=(ans+g[n][j][i][0]+g[n][j][i][1]);
			// if(i==n)cout<<"!"<<j<<' '<<i<<' '<<g[n][j][i][0]+g[n][j][i][1]<<endl;
		}
		// cerr<<ans<<' '<<val<<endl;
		printf("%.7Lf\n",ans/val);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5

output:

1.0000000
2.3000000
4.5000000

result:

ok 3 numbers

Test #2:

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

input:

5 17

output:

1.1313833
2.7483840
5.1830963
8.8556884
15.0000000

result:

ok 5 numbers

Test #3:

score: -100
Time Limit Exceeded

input:

50 10000

output:


result: