2015
05-23

# Game

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 229    Accepted Submission(s): 85

Problem Description
There are N people playing a game. The rules of the game are described as follows:
Initially, there are N people numbered from 1-N. And they are arranged in a queue by the order from 1-N. Each round, only 4 people get into the game and each people has equally probability to win the game. The winner can continue to games, the loser will go
to the end of the queue according to the order before this round (if someone was the winner before this round, we can consider he was the head of the queue).
The first round of game, the first four people start to play the game. If someone continuously wins the game M times, he will become the final winner.
Now I want to know the probability for the K-th people to become the final winner.

Input
The first line of input contains T, the number of test cases.
Flowing T line, each line contains 3 integer N, M, K.(4<=N<=10, M<=10,K<=N)

Output
Each output should occupy one line. Each line should start with "Case #i : ", followed by the answer round to six decimal places.

Sample Input
3
4 1 1
5 1 5
5 2 1

Sample Output
Case #1: 0.250000
Case #2: 0.000000
Case #3: 0.217626

Author
BJTU

Source

Recommend
zhoujiaqi2010

x1先赢了i局，正在于x2,x3,x4赌斗，后面依次有x5,x6,……,xn等待。用P[i][j]表示x1先赢了i局的情况下，当前的xj获胜的概率。

dp[i][j]表示第一个人已经赢了i次，当前第j个人能赢的概率。

1、i<m,

2、dp[m][1]=1，表示第一个人已经赢了m次，结束。

题目地址：Game

AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;

#define maxn 102
#define eps 1e-10
double g[maxn][maxn];
double x[maxn];
int n,m,k;

void add(int cnt,int i,int j,double val)
{
int t=i*n+j;
if(i==m)
{
if(j==1)    //p[m][1]=1;结束
g[cnt][m*n+1]+=-1.0*val;  //方程的右边
return;
}
g[cnt][t]+=val;
}

void gauss(int n,int m)
{
int row,col,i,j,k;
for(row=1,col=1;row<n,col<m;row++,col++)
{
k=row;
for(i=row+1;i<=n;i++)  //列主元
if(fabs(g[i][col])>fabs(g[k][col]))
k=i;
if(k!=row)   //行交换
{
for(i=col; i<=m; i++)
swap(g[k][i],g[row][i]);
}

for(i=row+1; i<=n; i++)  //主元不是0把下面的行第一个值全部变为0
{
if(fabs(g[i][col])<eps)
continue;
double t=g[i][col]/g[row][col];
g[i][col]=0.0;
for(j=col+1;j<=m;j++)
g[i][j]-=t*g[row][j];
}
}

for(i=n;i>=1;i--)  //回代求解
{
x[i]=g[i][m];
for(j=i+1;j<=n;j++)
x[i]-=x[j]*g[i][j];
x[i]/=g[i][i];
}
}

int main()
{
int i,j,cs,nn=0;
scanf("%d",&cs);
while(cs--){
scanf("%d%d%d",&n,&m,&k);
memset(g,0,sizeof(g));
int cnt=0;
for(i=0;i<m;i++)  //i==m的时候只能在右边出现
for(j=1;j<=n;j++)
{
cnt++;
if(j==1)
{
}
else if(j==2)
{
}
else if(j==3)
{
}
else if(j==4)
{
}
else
{