Overview:
做 ASC 42 的 B 题的时候遇到的问题。。。ASC 42 的题目是：
初始有 m 元钱，目标是恰好拥有 n 元钱
每轮你可以压至多当前你所拥有的钱数进行赌博，p 的概率翻倍，q 的概率失去赌注。
至多进行 t 个回合，问最优策略下达到目标的概率。
(t <= 300, p < 50。)
YY 了一下结论，假设当前有 m 元钱，每次压 min(m, n-m) 就可以了。
加之题目限制很强，模拟 DP 一下就出来了。在 camp 群里遂问了一下 p >= 50 的情况下结论还成立吗。。
果然有完整版的题目。
Problem C. Casino
初始有 m 元钱，目标是拥有 >= n 元钱，
每轮你可以压至多当前你所拥有的钱数进行赌博（必须整数），p 的概率翻倍，(1-p) 的概率失去赌注。
问最优策略下达到目标的概率，以及所有合法的第一步的方案（超过 200 个只需输出最大和最小的 100 个）。
（0 <= p <= 1, 0 < m < n <= 10^9)
首先特判掉 p = 1 或 p = 0 的边界情况。（由于结局固定，所以 [1, m] 都是合法解，即使加上去会超过 n。）
考虑和 ASC 那题的主要不同，主要是数据范围变大，并且没有了压住次数的限制。
那么首先考虑 p = 0.5 的情况，每轮赌注的期望收益都为 0，（与压多少无关）。
根据鞅论中的可选停止定理。停时的鞅的期望值等于其初始值，因而在 n 终止的概率为 m/n。
（所有 [1, min(m, n-m)] 的值都为合法解）
另外两种情况，直观的看上去。。。
- p > 0.5 时，平均起来，赌徒赢了钱，则随着时间的流逝，赌徒的财产是一个下鞅。
因而我们希望采取一种 “步步为营” 的策略，滚雪球，慢慢的积累自己的优势。
（直感：期待値的には良いわけだから長時間やってれば勝てるっしょ！） - p < 0.5 时，平均起来，赌徒输了钱，则随着时间的流逝，赌徒的财产是一个上鞅。 因而我们希望采取一种 “宁为玉碎” 的策略，一小博大，去希冀毕其功于一役！ （直感：期待値的に不利だから長引くとジリ貧，わんちゃん狙っていくしかない！）
因而前者我们每次只压 1，后者我们每次压 min(m, n-m)。
。。。Is that true?…
先证明前者。。
令 $$q = 1-p, r = \frac{q}{p}, f_x $$ 表示当前有 $$x$$ 时的期望，假设每次只压 1，我们有：
f[m] = pf[m+1] + qf[m-1]
f[0] = 1
f[1] = 0
解得：$$, f_m = \frac{1-r^m}{1-r^n}$$。(随机徘徊。。。
考虑反证法，如果不一定是每次只压 1，那么上面只能是不等式，首先有 $$f_m \geq \frac{1-r^m}{1-r^n}$$
再者如果存在 1 以外的最优方案，假设为 d，那么有
$$f_m = pf_{m+d} + qf_{m-d} \geq p\frac{1-r^{m+d}}{1-r^n} + q\frac{1-r^{m-d}}{1-r^n} $$
。。。我们要证明这个值 < $\frac{1-r^m}{1-r^n}$。
化简一下得：$$ 1-pr^{m+d}-qr^{m-d} < 1-r^m$$？
。。。但是我好像推不过去。。。
换个方法。。。
把 d 的情况看作是若干 1 的情况叠加成的（+-d 时停止）。。
那么为了得到 +d，我们要么一步走过去 p。
要么通过若干 1 的情况叠加过去。。。($$\frac{1-r^d}{1-r^{2d}}$$)
通过一些微积分的知识。。。（http://www.wolframalpha.com/input/?i=%281-%28%281-p%29%2Fp%29%5E2%29+-+%281-%28%281-p%29%2Fp%29%5E%284%29%29+p…
可以推断出后者在 p>1/2 的情况下是大于 p 的。。
因而此时最优方案为 1。
Problem L. Wall Making Game
https://discuss.codechef.com/questions/26237/caos3-editorial
//}/* .................................................................................................................................. */
const int N = int(20) + 9;
char Board[N][N]; int SG[N][N][N][N];
int h, w;
int sg(int x0, int y0, int x1, int y1){
int &z = SG[x0][y0][x1][y1];
if (z == -1){
if (x0 >= x1 || y0 >= y1) z = 0;
else{
set<int> H; FOR(x, x0, x1) FOR(y, y0, y1){
if (Board[x][y] == '.'){
H.insert(sg(x0, y0, x, y) ^ sg(x0, y+1, x, y1) ^
sg(x+1, y0, x1, y) ^ sg(x+1, y+1, x1, y1)) ;
}
}
REP(i, H.size()+1) if (H.find(i) == H.end()){
z = i;
break;
}
}
}
return z;
}
int main(){
#ifndef ONLINE_JUDGE
//freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
while (cin >> h >> w){
REP(i, h) scanf("%s", Board[i]); FLC(SG, -1);
puts(sg(0, 0, h, w) ? "First" : "Second");
}
}
