首页 > ACM题库 > HDU-杭电 > HDU 4136-Wimbledon-动态规划-[解题报告]HOJ
2015
04-16

HDU 4136-Wimbledon-动态规划-[解题报告]HOJ

Wimbledon

问题描述 :

I’m flying back to Cairo tomorrow, and do you know what is sad about that? Well, in addition to leaving beautiful Lebanon? Yep, I’m going to miss the 2011 Wimbledon final match which is going to happen while I’m 20,000 feet above sea level!
But hey, wait! I may have a shot here! At Wimbledon, matches are played only at day light, so maybe if players were not ready to give up easily on each point, then the match will extend until sunset, and the match would be suspended and resumed on Monday just for my convenience! So what I need to know is how long on average a game between two players will last, and to help me feel better you should write a computer program to determine that!
The result of a tennis match is determined by the number of “sets” each player wins, the first player to win three sets wins the match. Accordingly, all possible match results are 3-0, 3-1 and 3-2. The result of each set is determined by the number of “games” in the set each player wins, the first player to win six or more games with two or more game difference from the opponent wins the set, however if the result of a set (including the last set) leveled at 6-6 then a tie-break game is played to determine the set winner, Accordingly all possible set results are 6-0, 6-1, 6-2, 6-3, 6-4, 7-5 and 7-6 using a tie breaker game!
During each game (including tie-break), one player has the serve, this means that this player must start the play for all points of the game by hitting the ball, serving the ball is considered a big advantage. Assume that the serve starts at the first player and then alternates after each game till the end.
Given the probability of winning a game on serve for each player against his opponent, and assuming that each game lasts for five minutes, calculate the expected duration of the match.

输入:

The first line of input contains an integer T, the number of test cases.
The first line of each test case contains the first and last names of the first player, followed by an integer (0 <= A <= 100) where A/100 is the probability that the first player wins a game on his serve against the second player. The second line contains the first and last names of the second player, followed by an integer (0 <= B <= 100) where B/100 is the probability that the second player wins a game on his serve against the first player.

输出:

The first line of input contains an integer T, the number of test cases.
The first line of each test case contains the first and last names of the first player, followed by an integer (0 <= A <= 100) where A/100 is the probability that the first player wins a game on his serve against the second player. The second line contains the first and last names of the second player, followed by an integer (0 <= B <= 100) where B/100 is the probability that the second player wins a game on his serve against the first player.

样例输入:

2
Rafael Nadal 50
Roger Federer 50
Pete Sampras 100
Hamza Darwish 0

样例输出:

Case #1: 199.281006
Case #2: 90.000000
Hint
In the second test case, I don’t stand a chance against Pete! He always wins all games on his serve (probability 100/100) and he also always wins all games on my serve (as I win with probability 0/100), so he always wins the match with three straight sets (6-0, 6-0, 6-0), a total of 18 games played, each lasting five minutes for a total of 90 minutes match.


Wimbledon
Time
Limit: 1000ms, Special
Time Limit:2500ms, Memory
Limit:32768KB
Total submit
users: 2, Accepted
users: 2
Problem 12193 : No
special judgement
Problem
description
I’m
flying back to Cairo tomorrow, and do you know what is sad about
that? Well, in addition to leaving beautiful Lebanon? Yep, I’m
going to miss the 2011 Wimbledon final match which is going to
happen while I’m 20,000 feet above sea level!
But hey, wait! I may have a shot here! At Wimbledon, matches are
played only at day light, so maybe if players were not ready to
give up easily on each point, then the match will extend until
sunset, and the match would be suspended and resumed on Monday just
for my convenience! So what I need to know is how long on average a
game between two players will last, and to help me feel better you
should write a computer program to determine that!
The result of a tennis match is determined by the number of “sets”
each player wins, the first player to win three sets wins the
match. Accordingly, all possible match results are 3-0, 3-1 and
3-2. The result of each set is determined by the number of “games”
in the set each player wins, the first player to win six or more
games with two or more game difference from the opponent wins the
set, however if the result of a set (including the last set)
leveled at 6-6 then a tie-break game is played to determine the set
winner, Accordingly all possible set results are 6-0, 6-1, 6-2,
6-3, 6-4, 7-5 and 7-6 using a tie breaker game!
During each game (including tie-break), one player has the serve,
this means that this player must start the play for all points of
the game by hitting the ball, serving the ball is considered a big
advantage. Assume that the serve starts at the first player and
then alternates after each game till the end.
Given the probability of winning a game on serve for each player
against his opponent, and assuming that each game lasts for five
minutes, calculate the expected duration of the match.
Input
The first line of
input contains an integer T, the number of test cases. The first
line of each test case contains the first and last names of the
first player, followed by an integer (0 <= A <= 100) where
A/100 is the probability that the first player wins a game on his
serve against the second player. The second line contains the first
and last names of the second player, followed by an integer (0
<= B <= 100) where B/100 is the probability that the second
player wins a game on his serve against the first player.
Output
For each test
case, print the case number followed by the expected duration of
the match in minutes rounded to six decimal digits.
Sample Input
2
Rafael Nadal 50
Roger Federer 50
Pete Sampras 100
Hamza Darwish 0
Sample Output
Case #1: 199.281006
Case #2: 90.000000
Judge Tips
In the second test case,
I don’t stand a chance against Pete! He always wins all games on
his serve (probability 100/100) and he also always wins all games
on my serve (as I win with probability 0/100), so he always wins
the match with three straight sets (6-0, 6-0, 6-0), a total of 18
games played, each lasting five minutes for a total of 90 minutes
match.
Problem
Source
HNU Contest 
想法:宏观上每一场的情况都是等价的,所以没必要深搜三场,当每场有六种不同的情况,
i先发球j赢下一场该k先发球
(0=<=2),对应得要求出每种情况的时间期望。一开始还在纠结怎么求每种情况的时间期望,在dfs里面得到的是一场比赛每种情况的时间期望,但我想要求得是这场比赛在某种情况下的时间期望,后来突然想到直接用dfs得到的时间期望除以概率就可以了。
代码:
#include
#include
#include
#include
#include
using namespace
std;
#define eps
1e-10
#define N
100015
#define db
double
db
ans,p1,p2,win1,win2,win_num[2][2][2],dp[2][2][2];//dp[i][j][k]i先发球j赢下一次k先发球的概率
win_num[i][j][k]i先发球j赢下一次j先发球的时间期望
int sign(db
x){
  return (x > eps) – (x <
-eps);
}
void dfs(int pl1,db p,int
pl2,int v,int s){//球员0赢的球数 当前状态的概率 球员1赢的球数 轮到球员v发球
球员s第一个发球
  if((pl1 == 6&&pl2 <= 4)||pl1 ==
7){
win_num[s][0][v] += p*(pl1+pl2)*5.;
dp[s][0][v] += p;
      return
;
  }
  if((pl2 == 6&&pl1 <= 4)||pl2 ==
7){
win_num[s][1][v] += p*(pl1+pl2)*5.;
dp[s][1][v] += p;
      return
;
  }
  if(v)
dfs(pl1,p*p2,pl2+1,v^1,s),dfs(pl1+1,p*(1.-p2),pl2,v^1,s);
  else
dfs(pl1+1,p*p1,pl2,v^1,s),dfs(pl1,p*(1.-p1),pl2+1,v^1,s);
}
void dfs2(int l1,int l2,db
pl1,db p,db pl2,int v){//球员0赢的场数 球员1赢的场数 球员0赢的时间期望 当前状态概率 球员1赢的时间期望
轮到球员v发球
  if(l1 == 3||l2 == 3){
      ans +=
p*(pl1+pl2);
      return
;
  }
dfs2(l1+1,l2,pl1+win_num[v][0][0],dp[v][0][0]*p,pl2,0);
dfs2(l1+1,l2,pl1+win_num[v][0][1],dp[v][0][1]*p,pl2,1);
dfs2(l1,l2+1,pl1,dp[v][1][0]*p,pl2+win_num[v][1][0],0);
dfs2(l1,l2+1,pl1,dp[v][1][1]*p,pl2+win_num[v][1][1],1);
}
char s[256];
int main()
{
//freopen(“wimbledon.in”,”r”,stdin);
  //freopen(“output.out”,”w”,stdout);
  int T,cas = 1;
  int i,j,k;
  scanf(“%d”,&T);
  while(T–)
  {
scanf(“%s%s%lf”,&s,&s,&p1);
scanf(“%s%s%lf”,&s,&s,&p2);
      p1 /=
100.;
      p2 /=
100.;
      ans =
0.;
      for(i = 0;
i < 2; i ++) for(j = 0; j < 2; j ++) for(k = 0; k < 2; k
++) win_num[i][j][k] = dp[i][j][k] = 0.;
dfs(0,1.,0,0,0);//0先发球
dfs(0,1.,0,1,1);//1先发球
      for(i = 0;
i < 2; i ++) for(j = 0; j < 2; j ++) for(k = 0; k < 2; k
++) if(sign(dp[i][j][k])) win_num[i][j][k] /=
dp[i][j][k];
dfs2(0,0,0.,1.,0.,0);
printf(“Case #%d: %.6lf\n”,cas++,ans);
  }
return 0;
}
参考:http://blog.sina.com.cn/s/blog_6ffc3bde01018pyx.html


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧