QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#208244 | #4228. Double Sort | ucup-team1209# | AC ✓ | 30ms | 14488kb | C++20 | 1.6kb | 2023-10-09 11:52:47 | 2023-10-09 11:52:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
#ifdef zqj
freopen("a.in","r",stdin);
#endif
}
typedef long long ll;
typedef __float128 db;
#define sz 10010
int n,m;
db ans[sz];
db C[sz][66]; // check size
int main() {
file();
cin>>n>>m;
rep(i,0,sz-1) C[i][0]=1;
rep(i,1,sz-1) rep(j,1,min(i,n)) C[i][j]=C[i-1][j]+C[i-1][j-1];
// rep(k,1,n) rep(i,1,m) rep(j,0,k-1) {
// int mm=m-(n-j)*(i-1);
// if (mm<0) continue;
// // at most mm into n, where j of them be <i
// db res=0;
// rep(t,0,j) {
// int mmm=mm-t*(i-1);
// if (mmm<0) break;
// db w=((t&1)?-1:1)*C[j][t]*C[mmm][n];
// res+=w;
// }
// ans[k]+=res*C[n][j]/C[m][n];
// }
rep(k,1,n) {
std::vector<db> val(k+1);
rep(x,0,k-1) {
db w1=0;
rep(i,1,m) if ((n-x)*(i-1)<=m) w1+=C[m-(n-x)*(i-1)][n]/C[m][n];
db w2=0;
rep(j,0,k-x-1) w2+=(((j&1)?-1:1)*C[n-x][j]);
val[x]=C[n][x]*w1*w2;
}
for(int i=0;i<k;i+=2) {
// cout<<val[i]<<' '<<val[i+1]<<'\n';
ans[k]+=val[i]+val[i+1];
}
}
rep(i,1,n) ans[i]+=ans[i-1];
rep(i,1,n) printf("%.10Lf\n",(long double)ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 14212kb
input:
3 5
output:
1.0000000000 2.3000000000 4.5000000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 3ms
memory: 14092kb
input:
5 17
output:
1.1313833226 2.7483839690 5.1830963154 8.8556884292 15.0000000000
result:
ok 5 numbers
Test #3:
score: 0
Accepted
time: 28ms
memory: 14364kb
input:
50 10000
output:
4.4328164335 12.8365968668 25.3152687339 41.9556112383 62.8480760618 88.0871546758 117.7716337788 152.0048947778 190.8952420036 234.5562629251 283.1072243847 336.6735094732 395.3871003913 459.3871135128 528.8203938988 603.8421777570 684.6168328365 771.3186885683 864.1329699727 963.2568520715 1068.90...
result:
ok 50 numbers
Test #4:
score: 0
Accepted
time: 8ms
memory: 14096kb
input:
40 40
output:
1.0000000000 2.0000000000 3.0000000000 4.0000000000 5.0000000000 6.0000000000 7.0000000000 8.0000000000 9.0000000000 10.0000000000 11.0000000000 12.0000000000 13.0000000000 14.0000000000 15.0000000000 16.0000000000 17.0000000000 18.0000000000 19.0000000000 20.0000000000 21.0000000000 22.0000000000 2...
result:
ok 40 numbers
Test #5:
score: 0
Accepted
time: 10ms
memory: 14092kb
input:
39 1489
output:
1.5270875628 3.9390125652 7.3403302435 11.7634937450 17.2367013630 23.7907109205 31.4582877129 40.2742330903 50.2755910473 61.5018753030 73.9953246967 87.8011951264 102.9680947788 119.5483709315 137.5985586446 157.1799042332 178.3589797787 201.2084093701 225.8077336763 252.2444474329 280.6152553480 ...
result:
ok 39 numbers
Test #6:
score: 0
Accepted
time: 30ms
memory: 14488kb
input:
47 9871
output:
4.8839175854 14.2093220216 28.0939348059 46.6414309717 69.9602357807 98.1639517434 131.3717230464 169.7086510733 213.3062526631 262.3029665937 316.8447148205 377.0855260737 443.1882307257 515.3252374057 593.6794037510 678.4450160011 769.8288949916 868.0516496140 973.3491031658 1085.9739234660 1206.1...
result:
ok 47 numbers
Test #7:
score: 0
Accepted
time: 7ms
memory: 14088kb
input:
9 9999
output:
111.5562225553 348.0492603945 727.3280017986 1273.1900640301 2018.9521112541 3014.5891397187 4343.3928098375 6171.9464424375 9000.0000000000
result:
ok 9 numbers