QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#98953 | #5105. Hand of the Free Marked | uphargaur | TL | 3ms | 3668kb | C++20 | 1.2kb | 2023-04-21 01:58:42 | 2023-04-21 01:58:46 |
Judging History
answer
#include <iostream>
using namespace std;
int k, m, n, a[99], b[99];
long double ans, totnum, num, p;
long double fact(long double n);
long double nCr(long double n, long double r)
{
return fact(n) / (fact(r) * fact(n - r));
}
// Returns factorial of n
long double fact(long double n)
{
if(n==0)
return 1;
long double res = 1;
for (long double i = 2; i <= n; i++)
res = res * i;
return res;
}
void dfs(int nw, int sm) {
if (nw > m) {
if (sm ^ k)
return;
num = 1;
p = 0;
for (int i = 1; i <= m; ++i)
num *= nCr(a[i], b[i]), p += (long double)b[i] / (a[i] - b[i] + 1);
for (int i = 1; i < k; ++i)
p *= i;
if (p > 1)
ans += num / totnum;
else
ans += num / totnum * p;
return;
}
for (int i = 0; i + sm <= k && i <= a[nw]; ++i)
b[nw] = i, dfs(nw + 1, sm + i);
}
int main() {
cin >> k >> m;
for (int i = 1; i <= m; ++i)
cin >> a[i], n += a[i];
totnum = nCr(n, k);
dfs(1, 0);
cout.precision(10);
cout << fixed << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3480kb
input:
3 3 2 1 2
output:
1.0000000000
result:
ok answer is 1.0000000000
Test #2:
score: 0
Accepted
time: 2ms
memory: 3468kb
input:
3 4 1 3 1 15
output:
0.7719298246
result:
ok answer is 0.7719298246
Test #3:
score: 0
Accepted
time: 2ms
memory: 3476kb
input:
4 1 27
output:
1.0000000000
result:
ok answer is 1.0000000000
Test #4:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
4 3 1 2 28
output:
0.9739710790
result:
ok answer is 0.9739710790
Test #5:
score: 0
Accepted
time: 2ms
memory: 3664kb
input:
4 3 1 3 28
output:
0.9772246941
result:
ok answer is 0.9772246941
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
5 1 130
output:
0.9523809524
result:
ok answer is 0.9523809524
Test #7:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
5 3 2 16 200
output:
0.7490392123
result:
ok answer is 0.7490392123
Test #8:
score: 0
Accepted
time: 2ms
memory: 3540kb
input:
4 10 1 2 3 4 1 2 3 4 5 100
output:
0.6954998646
result:
ok answer is 0.6954998646
Test #9:
score: 0
Accepted
time: 3ms
memory: 3668kb
input:
4 10 1 20 3 4 1 2 40 4 5 500
output:
0.2435721816
result:
ok answer is 0.2435721816
Test #10:
score: -100
Time Limit Exceeded
input:
3 2 152333146 373955979