UVA 10417 Gift Exchanging

#include <iostream>
#include <cstring>
#include <stdio.h>
#include <math.h>
#define N 12
using namespace std;

int n;
int expect[6]; //5种礼物的实际数量
double p[N][6];
double first[6];

void Input()
{
    int i,j;
    scanf("%d", &n);
    for(j=1;j<=5;j++)
    {
        scanf("%d", &expect[j]);
    }
    for(i=0;i<n;i++)
    {
        for(j=1;j<=5;j++)
        {
            scanf("%lf", &p[i][j]);
        }
    }
    memset(first,0,sizeof(first));
}

double dfs(int g, double c)
{
    if(g==n)
    return c;
    double t;
    double ans=0;
    for(int i=1;i<=5;i++)
    {
        if(expect[i]&&fabs(p[g][i])>1e-9)
        {
            expect[i]--;
            t = dfs(g+1, c*p[g][i]);
            if(g==0)
                first[i]+=t;
            expect[i]++;
            ans+=t;
        }
    }
    return ans;
}

void Do(double s)
{
    int x;
    double v=0;
    for(int i=1;i<=5;i++)
    {
        if(first[i]/expect[i]-v > 1e-9)
        {
            x=i;
            v=first[i]/expect[i];
        }
    }
    printf("%d %.3lf
",x,v/s);
}

int main()
{
    int t;
    double s;
    scanf("%d", &t);
    while(t--)
    {
        Input();
        s=dfs(0, 1);
        Do(s);
    }
    return 0;
}