QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#58545 | #4228. Double Sort | xiaoyaowudi | WA | 4ms | 13160kb | C++17 | 842b | 2022-10-26 20:23:00 | 2022-10-26 20:23:02 |
Judging History
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'