QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#885418 | #4228. Double Sort | jryggs | WA | 0ms | 6104kb | C++14 | 1.4kb | 2025-02-06 15:34:27 | 2025-02-06 15:34:36 |
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++){
// cerr<<i<<' '<<j<<' '<<f[i][j]<<endl;
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]);
// cout<<"!"<<j<<' '<<i<<' '<<g[n][j][i][0]+g[n][j][i][1]<<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: 5972kb
input:
3 5
output:
1.0000000 2.3000000 4.5000000
result:
ok 3 numbers
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 6104kb
input:
5 17
output:
0.8720103 2.2013575 4.2821590 7.4957983 12.9734971
result:
wrong answer 1st numbers differ - expected: '1.1313833', found: '0.8720103', error = '0.2292530'