QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#786960#4228. Double Sort通顶雪道 (Qiuyang Mang, Youran Sun, Qingshuo Guo)TL 22ms14196kbC++14843b2024-11-27 03:31:562024-11-27 03:31:56

Judging History

This is the latest submission verdict.

  • [2024-11-27 03:31:56]
  • Judged
  • Verdict: TL
  • Time: 22ms
  • Memory: 14196kb
  • [2024-11-27 03:31:56]
  • Submitted

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...

result: