QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#502780 | #4228. Double Sort | ZhouShang | AC ✓ | 336ms | 241552kb | C++20 | 1.3kb | 2024-08-03 13:50:51 | 2024-08-03 13:50:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for (int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int, k>
template<class A, class B> void cmx(A &x, B y) { x = max<A>(x, y);}
template<class A, class B> void cmn(A &x, B y) { x = min<A>(x, y);}
typedef pair<int, int> pii;
typedef vector<int> vi;
int n,m;
double c[10009][59],f[59][10009][59];
double C(int n,int m){
if(!(0<=n&&n<=10000&&0<=m&&m<=50))
return 0;
return c[n][m];
}
signed main() {
//cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
cin>>n>>m;
for(int i=0;i<=10000;i++)
for(int j=0;j<=min(50ll,i);j++)
c[i][j]=!j?1:c[i-1][j]+c[i-1][j-1];
for(int i=1;i<=n;i++)
for(int j=i;j<=m;j++){
for(int k=1;k<=i;k++)
f[i][j][k]=k;
for(int k=0;k<=i;k++){
double p=1.0*C(j-i,k)*C(i,k)/C(j,i);
if(p==0)
continue;
for(int l=1;l<=k;l++)
f[i][j][i-k+l]+=p*f[k][j-i][l];
}
}
for(int i=1;i<=n;i++)
cout<<fixed<<setprecision(9)<<f[n][m][i]<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15628kb
input:
3 5
output:
1.000000000 2.300000000 4.500000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 20716kb
input:
5 17
output:
1.131383323 2.748383969 5.183096315 8.855688429 15.000000000
result:
ok 5 numbers
Test #3:
score: 0
Accepted
time: 336ms
memory: 241552kb
input:
50 10000
output:
4.432816434 12.836596867 25.315268734 41.955611238 62.848076062 88.087154676 117.771633779 152.004894778 190.895242004 234.556262925 283.107224385 336.673509473 395.387100391 459.387113513 528.820393899 603.842177757 684.616832836 771.318688568 864.132969973 963.256852072 1068.900654888 1181.2892032...
result:
ok 50 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 92672kb
input:
40 40
output:
1.000000000 2.000000000 3.000000000 4.000000000 5.000000000 6.000000000 7.000000000 8.000000000 9.000000000 10.000000000 11.000000000 12.000000000 13.000000000 14.000000000 15.000000000 16.000000000 17.000000000 18.000000000 19.000000000 20.000000000 21.000000000 22.000000000 23.000000000 24.0000000...
result:
ok 40 numbers
Test #5:
score: 0
Accepted
time: 16ms
memory: 117016kb
input:
39 1489
output:
1.527087563 3.939012565 7.340330244 11.763493745 17.236701363 23.790710921 31.458287713 40.274233090 50.275591047 61.501875303 73.995324697 87.801195126 102.968094779 119.548370932 137.598558645 157.179904233 178.358979779 201.208409370 225.807733676 252.244447433 280.615255348 311.027607097 343.601...
result:
ok 39 numbers
Test #6:
score: 0
Accepted
time: 278ms
memory: 226996kb
input:
47 9871
output:
4.883917585 14.209322022 28.093934806 46.641430972 69.960235781 98.163951743 131.371723046 169.708651073 213.306252663 262.302966594 316.844714820 377.085526074 443.188230726 515.325237406 593.679403751 678.445016001 769.828894992 868.051649614 973.349103166 1085.973923466 1206.197494468 1334.312075...
result:
ok 47 numbers
Test #7:
score: 0
Accepted
time: 13ms
memory: 51460kb
input:
9 9999
output:
111.556222555 348.049260394 727.328001799 1273.190064030 2018.952111254 3014.589139719 4343.392809837 6171.946442438 9000.000000000
result:
ok 9 numbers