D. Darts

題意：在指定的飛鏢盤上有數字1~20，玩家A隨機（1/20）扔飛鏢，玩家B可以選擇連續的三塊等概率（1/3）扔飛鏢，若A扔出的數字為 k k k，A的得分為 a a a，B的得分為 b b b，則此時 b ? = k b-=k b?=k，若 k > b k>b k>b就當無事發生，當且僅當 k = b k=b k=b時A獲勝；B的回合同理，求玩家A和B分別先手的勝率，

決議：經典概率dp，設 f [ 0 / 1 ] [ i ] [ j ] f[0/1][i][j] f[0/1][i][j]為該A/B扔飛鏢時，A還剩 i i i分，B還剩 j j j分時A/B的勝率，顯然有轉移：

f [ 0 ] [ i ] [ j ] = ∑ ( 1 ? f [ 1 ] [ i ] [ j ? p [ 1...20 ] ] ) 20 f[0][i][j]=\frac{\sum{(1-f[1][i][j-p[1...20]])}}{20} f[0][i][j]=20∑(1?f[1][i][j?p[1...20]])?

f [ 1 ] [ i ] [ j ] = max ? { ∑ ( 1 ? f [ 0 ] [ i ? p [ k / k + 1 / k + 2 ] ] [ j ] ) } 3 f[1][i][j]=\frac{\max\{\sum{(1-f[0][i-p[k/k+1/k+2]][j])}\} }{3} f[1][i][j]=3max{∑(1?f[0][i?p[k/k+1/k+2]][j])}?

然而要是這么簡單就結束了，過的人不會這么少（

實際上，當 i ≤ 20 ∣ ∣ j ≤ 20 i\le20||j\le20 i≤20∣∣j≤20時，情況發生了微妙的改變，

首先，顯然 i ≤ 20 & & j ≤ 20 i\le20\&\&j\le20 i≤20&&j≤20時，答案都是確定的，這里樣例里的 n = 5 n=5 n=5給出了結果，

在轉移的時候，由于 p [ k ] > a p[k]>a p[k]>a無事發生，就會存在 f [ 0 ] [ i ] [ j ] f[0][i][j] f[0][i][j]到 f [ 1 ] [ i ] [ j ] f[1][i][j] f[1][i][j]的轉移以及 f [ 1 ] [ i ] [ j ] f[1][i][j] f[1][i][j]到 f [ 0 ] [ i ] [ j ] f[0][i][j] f[0][i][j]的轉移，

啊這，成環了該怎么dp啊？

但是觀察發現，其實只有 f [ 0 ] [ i ] [ j ] f[0][i][j] f[0][i][j]和 f [ 1 ] [ i ] [ j ] f[1][i][j] f[1][i][j]之間的相互轉移，也就是說只存在兩個未知數，

那么問題就解決了，怎么辦？解方程！

設 A = f [ 0 ] [ i ] [ j ] , B = f [ 1 ] [ i ] [ j ] A=f[0][i][j],\ B=f[1][i][j] A=f[0][i][j], B=f[1][i][j]，則有

A = t 1 + c 1 ( 1 ? B ) A=t_1+c_1(1-B) A=t1?+c1?(1?B)

B = t 2 + c 2 ( 1 ? A ) B=t_2+c_2(1-A) B=t2?+c2?(1?A)

而且，由于B可以選擇投擲策略，我們就先解出 B B B的值，易得

B = t 2 + c 2 ? t 1 c 2 ? c 1 c 2 1 ? c 1 c 2 B=\frac{t_2+c_2-t_1c_2-c_1c_2}{1-c_1c_2} B=1?c1?c2?t2?+c2??t1?c2??c1?c2??

t 1 , t 2 , c 1 , c 2 t_1,t_2,c_1,c_2 t1?,t2?,c1?,c2?都可以在回圈里求出來，取最大值就能得到 B B B即 f [ 1 ] [ i ] [ j ] f[1][i][j] f[1][i][j]了，問題就這么愉快的解決了，

代碼：

#include<bits/stdc++.h>
#define db long double
#define _S(...) scanf(__VA_ARGS__)
#define _P(...) printf(__VA_ARGS__)
#define GKD ios::sync_with_stdio(false)
using namespace std;
const db EPS=1e-8;
const int N=520;
const int LIM=501;
const int p[20]={1,18,4,13,6,10,15,2,17,3,19,7,16,8,11,14,9,12,5,20};
int n;
db f[2][N][N];//0:A, 1:B
int main()
{
    for(int i=1;i<=20;i++)
    {
        f[0][0][i]=f[1][i][0]=0;
        f[1][0][i]=f[0][i][0]=1;
    }
    for(int i=1;i<=20;i++)
    {
        for(int j=1;j<=20;j++)
        {
            f[0][i][j]=0.136363636364;
            f[1][i][j]=0.909090909091;
        }
    }
    for(int i=1;i<=LIM;i++)
    {
        for(int j=1;j<=LIM;j++)
        {
            if(i<=20&&j<=20)continue;
            db c1=0,c2=0,t=0,t1=0,t2=0;
            for(int k=0;k<20;k++)//A-go
            {
                if(j-p[k]<0)c1++;
                else t1+=(1.0-f[1][i][j-p[k]]);
            }
            c1/=20.0,t1/=20.0;
            for(int k=0;k<20;k++)//B-go
            {
                c2=t2=0;
                for(int l=0;l<3;l++)
                {
                    if(i-p[(k+l)%20]<0)c2++;
                    else t2+=(1.0-f[0][i-p[(k+l)%20]][j]);
                }
                c2/=3.0,t2/=3.0;
                t=max(t,(t2+c2-t1*c2-c1*c2)/(1-c1*c2));
            }
            f[1][i][j]=t;
            f[0][i][j]=t1+c1*(1.0-t);
        }
    }
    GKD;
    while(_S("%d", &n), n)
    {
        _P("%.12Lf %.12Lf\n",f[0][n][n],f[1][n][n]);
    }
}