QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#390620#5105. Hand of the Free Marked0_GB_RAMWA 1ms3928kbC++231.8kb2024-04-15 18:25:342024-04-15 18:25:34

Judging History

你现在查看的是最新测评结果

  • [2024-04-15 18:25:34]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3928kb
  • [2024-04-15 18:25:34]
  • 提交

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";
}

詳細信息

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