QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#390620 | #5105. Hand of the Free Marked | 0_GB_RAM | WA | 1ms | 3928kb | C++23 | 1.8kb | 2024-04-15 18:25:34 | 2024-04-15 18:25:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) (int)((x).size())
using pii=pair<int,int>;
using vi=vector<int>;
#define fi first
#define se second
#define pb push_back
int n, k;
int y[11];
int x[11];
double ans = 0.0;
int f;
double cnk(int n, int k)
{
if (k > n-k)
return cnk(n, n-k);
double ans = 1;
for (int i=1; i<=k; i++)
ans *= n-k+i, ans/=i;
return ans;
}
void process()
{
// for (int i=0; i<n; i++)
// cout<<x[i]<<"/"<<y[i]<<" ";
// cout<<"\n";
double mx = 0;
for (int i=0; i<k; i++) {
int p = f / k * x[i];
int q = y[i] - x[i] + 1;
mx = max(mx, p*1.0/q);
}
int yx1 = 0;
double avg = 0;
for (int i=0; i<k; i++)
{
avg += x[i]*1.0/(y[i]-x[i]+1);
yx1 = max(yx1, y[i]-x[i]+1);
}
avg /= k;
mx = max(mx, f * 1.0 / yx1);
mx = max(mx, f * avg);
mx = min(mx, 1.0);
double v = 1;
for (int i=0; i<k; i++)
{
v *= cnk(y[i], x[i]);
}
ans += v*mx;
}
void brute(int i, int sum)
{
if (i == n-1)
{
x[i] = k - sum;
if (x[i] > y[i])
return;
process();
return;
}
for (x[i] = 0; sum + x[i] <= k && x[i] <= y[i]; x[i]++)
brute(i+1, sum+x[i]);
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cout<<fixed<<setprecision(10);
cin>>k>>n;
int s = 0;
for (int i=0; i<n; i++)
cin>>y[i], s += y[i];
f = 1;
for (int i=1; i<=k; i++)
f*=i;
brute(0, 0);
ans /= cnk(s, k);
cout<<ans<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3880kb
input:
3 3 2 1 2
output:
1.0000000000
result:
ok answer is 1.0000000000
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3928kb
input:
3 4 1 3 1 15
output:
0.0228070175
result:
wrong answer expected 0.7719298246, found 0.0228070175