 /**//*
題意:在一個圓形靶(20個數字)上,A,B兩人扔飛鏢
A是隨意扔,B是朝著目標扔,不過有可能扔中目標的左右兩格
起始,每個人有分值n,扔中某個數字n-該數字,如果該數字>n,則不減
誰先減為0,誰贏
現計算A,B兩人各先扔時,贏的概率(每一次,兩人是輪流扔的)

由于投的次數可以無限的,其實確定狀態只需要知道A,B目前的分數即可了!!

pA[n,m] 表示A當前分值為n,B為m時,A現在扔了后贏的概率
pB[n,m] 表示A當前分值為n,B為m時,B現在扔了后贏的概率
pA[n,m] = 1/20*∑ {(1-pB[n-i,m])}
pB[n,m] = max{1/3*∑ (1-pA[n][m-d(i+j)])}
上式是對于n>20,m>20時成立的
n<20 || m<20時,因為有可能扔了后那個數字比自身還大,則不減,即
p[n,m] <- p[n,m]
由自身決定,有環,解這樣的方程組可以迭代 ★★★★★
現賦給他們最低限度的值,然后普通那樣子算 ★★★★★
*/
#include<cstdio>
#include<algorithm>

using namespace std;

const int MAXN = 502;

double pA[MAXN][MAXN];
double pB[MAXN][MAXN];

 int board[22] = {5,20,1,18,4,13,6,10,15,2,17,3,19,7,16,8,11,14,9,12,5,20};

 inline int next(int a,int b) {return a>=b?a-b:a;}

void init()
  {
for(int i=0;i<MAXN;i++)pA[0][i] = 1.0;
for(int i=0;i<MAXN;i++)pB[i][0] = 1.0;

for(int n=1;n<MAXN;n++)
for(int m=1;m<MAXN;m++)
 {
//最低限度的值
if(n<=20)pA[n][m] = 1/20.0;//扔中n的概率就是1/20
if(m<=20)pB[n][m] = 1/3.0;//扔中目標的概率就是1/3
for(int it = 0;it<50;it++)
 {
//pA[n,m] = 1/20*∑ {(1-pB[n-i,m])}
pA[n][m] = 0.0;
for(int i=1;i<=20;i++)
pA[n][m] += (1-pB[next(n,i)][m])/20.0;
//pB[n,m] = max{1/3*∑ (1-pA[n][m-d(i+j)])}
// = 1 - min{1/3*∑pA[n][m-d(i+j)]}
double val = 1e300;
for(int i=1;i<=20;i++)
 {
double t = 0;
for(int j=-1;j<=1;j++)
t += pA[n][next(m,board[i+j])];
t/=3;
val = min(val,t);
}
pB[n][m] = 1 - val;
if(n>20 && m>20)break;
}
}
}

int main()
  {
// freopen("in","r",stdin);
init();
int n;
while(scanf("%d",&n),n)
printf("%.12f %.12f\n",pA[n][n],pB[n][n]);

return 0;
}
|