QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#885428 | #4228. Double Sort | jryggs | WA | 0ms | 5916kb | C++14 | 1.4kb | 2025-02-06 15:37:36 | 2025-02-06 15:37:37 |
Judging History
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]+f[i][j][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: 0
Wrong Answer
time: 0ms
memory: 5916kb
input:
3 5
output:
1.0000000 2.6000000 5.7000000
result:
wrong answer 2nd numbers differ - expected: '2.3000000', found: '2.6000000', error = '0.1304348'