QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786960 | #4228. Double Sort | 通顶雪道 (Qiuyang Mang, Youran Sun, Qingshuo Guo) | TL | 22ms | 14196kb | C++14 | 843b | 2024-11-27 03:31:56 | 2024-11-27 03:31:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
const int maxm = 10005;
int n, m;
long double binom[maxm][maxn];
long double f[maxn][maxm][maxn];
int main(){
scanf("%d%d", &n, &m);
for (int i = 0; i < maxm; ++i) for (int j = 0; j < maxn && j <= i; ++j) {
binom[i][j] = 1;
for (int k = 0; k < j; ++k) binom[i][j] *= (long double)(i - k) / (long double)(j - k);
}
for (int i = 1; i <= n; ++i) for (int j = i; j <= m; ++j) {
for (int k = 0; k <= i; ++k) {
long double res = binom[j - i][k] * binom[i][k];
for (int x = 1; x <= k; ++x) f[i][j][x + i - k] += res * f[k][j - i][x];
}
for (int x = 1; x <= n; ++x) f[i][j][x] /= binom[j][i];
for (int x = 1; x <= n; ++x) f[i][j][x] += x;
}
for (int k = 1; k <= n; ++k) printf("%.10Lf ", f[n][m][k]); puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 22ms
memory: 14196kb
input:
3 5
output:
1.0000000000 2.3000000000 4.5000000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 14ms
memory: 12604kb
input:
5 17
output:
1.1313833226 2.7483839690 5.1830963154 8.8556884292 15.0000000000
result:
ok 5 numbers
Test #3:
score: -100
Time Limit Exceeded
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...