Poker End Games

題目鏈接

題意：
初始為一個數對（a，b），每回合從a到b或者從b到a轉移min（a，b），最後如果b為零，獲勝
求能進行的回合數的期望和獲勝的概率
For both these valueserrors less than 10e-5will be ignored
分析：
這個題目關鍵在於誤差為1e-5比較大，所以其實不用高斯消元，直接DFS忽略環形。因為大約遞歸20層左右就可以結束了（此時近似為0），所以暴力DFS即可

const double EPS = 1e-8;

using namespace std;

int sum;
double rd, win;
void dfs(int a, int lev, double p)
{
	if (p < EPS) return;
	if (a == 0)
	{
		rd += lev * p;
		return;
	}
	else if (a == sum)
	{
		rd += lev * p;
		win += p;
		return;
	}
	int Min = min(a, sum - a);
	dfs(a - Min, lev + 1, p * 0.5);
	dfs(a + Min, lev + 1, p * 0.5);
}

int main()
{
	int T, a, b;
	RI(T);
	FE(kase, 1, T)
	{
		RII(a, b);

		rd = win = 0;
		sum = a + b;
		dfs(a, 0, 1);
		printf("Case %d: %.6f %.6f\n", kase, rd, win);
	}
    return 0;
}