Kick the ball!（dfs）湖南省赛第十届

Problem K: Kick the ball!

Time Limit: 1 Sec Memory Limit: 128 MB Special Judge

Submit: 109 Solved: 82

[Submit][Status][Web
Board]

Description

"A penalty shoot-out (officially kicks from the penalty mark) is a method of determining the winner of an association football (soccer) match that is drawn after the regulation playing time and any applicable extra time periods have been played. In a penalty
shoot-out, each team takes turns attempting a specified number of shots from the penalty mark (usually 5) that are only defended by the opposing team's goalkeeper, with the team scoring the most goals being declared the winner."

-- wikipedia

The game finally comes to the shoot-out. What will the final result be?

"1-3!" You took a wild guess. But what is the probability that your guess is correct?

In this problem, team A kicks first (which is determined by a coin toss, as usual), both teams will attempt at most 5 shots (after all the 10 shots, the game may end in draw again), but the game will end as soon as the winner is already determined. For example,
after the first 8 kicks the score is 3-2 (left side is team A’s score, right side is team B), then if the 9-th kick is a goal, the game will end immediately with score 4-2, because even team B got its last kick, it still loses for sure. Another example: if
all the first 9 kicks are goals, the last kick (from team B) will still be performed, because although team B cannot win, the result might be a "draw", which is better than "lose".

Input

There will be at most 100 test cases. Each case contains two lines. The first line contains 10 floating numbers. The first 5 numbers are the goal probability of the players in team A (player 1 will shoot first, etc), the next 5 numbers are the goal probabilities
of the players in team B. Each probability will have exactly one digit after the decimal point. The second line contains your guess, in the format of scoreA-scoreB. 0<=scoreA,scoreB<=5.

Output

For each test case, print the case number and the probability (in percentage) that your wild guess is correct, to 2 decimal places. An absolute error of 0.01% will be ignored.

Sample Input

0.4 0.7 0.7 0.6 0.5 0.8 0.9 0.7 0.2 0.8

1-3

1.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0

2-0

1.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0

2-0

0.4 0.7 0.7 0.6 0.5 0.8 0.9 0.7 0.2 0.8

5-5

0.4 0.7 0.7 0.6 0.5 0.8 0.9 0.7 0.2 0.8

4-2

Sample Output

Case 1: 6.98%

Case 2: 100.00%

Case 3: 0.00%

Case 4: 0.47%

Case 5: 9.73%

HINT

题意：点球大战，轮流每队点射5个球。A先踢。A、B轮流踢，假设当前比分已经能直接让比赛胜利接下来的球就不须要踢了。问最后的得分是题所给出的得分的概率

思路：暴力DFS，直接枚举哪些球进了哪些球没进，注意比赛提前结束这个特殊的剪枝即可。

链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?

cid=2095&pid=10

#include<stdio.h>

double pi[15];

int x;

int y;

double ans;

bool judge(int a,int b,int t)

{

    if(a-b-(t+1)/2>0) return true;//a>b,假设推断的这个点是b点。那么t是奇数须要(t+1)/2，假设是a点t为偶数t/2=(t+1)/2

    if(b-a-t/2>0) return true;//b>a,假设推断的这个点是b点，那么t是奇数须要(t+1)/2个求能够胜，可是b>a了。所以假设这球不得分，假设是a点t为偶数t/2=(t+1)/2

    return false;

}

void dfs(int a,int b,int k,double p)

{

    if(p<1e-6) return ;

    if(k==10)

    {

       // printf("a=%d,b=%d\n",a,b);

        if(a==x&&b==y)

            ans+=p;

        return ;

    }

    if(judge(a,b,10-k))//推断这一脚要不要踢

    {

        dfs(a,b,k+1,p);

        return ;

    }

    if(k&1)

    {

        dfs(a,b+1,k+1,p*pi[k]);

        dfs(a,b,k+1,p*(1-pi[k]));

    }

    else

    {

        dfs(a+1,b,k+1,p*pi[k]);

        dfs(a,b,k+1,p*(1-pi[k]));

    }

}

int main()

{

    int ca=1;

    while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&pi[0],&pi[2],&pi[4],&pi[6],&pi[8],&pi[1],&pi[3],&pi[5],&pi[7],&pi[9])!=EOF)

    {

        scanf("%d-%d",&x,&y);

   //     printf("x=%d,y=%d\n",x,y);

        ans=0;

        dfs(0,0,0,1.0);

        printf("Case %d: %.2f%%\n",ca++,ans*100.0);

    }

    return 0;

}

/*

0.4 0.7 0.7 0.6 0.5 0.8 0.9 0.7 0.2 0.8

1-3

1.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0

2-0

1.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0

2-0

0.4 0.7 0.7 0.6 0.5 0.8 0.9 0.7 0.2 0.8

5-5

0.4 0.7 0.7 0.6 0.5 0.8 0.9 0.7 0.2 0.8

4-2

*/

巴特西