[YNOI2019] 游戏
题外话
第一眼，由乃？不打不打。
第二眼，欸 noi 三个字母怎么是大写（才发现是云南省选）。
题意
题意简洁，不再赘述。
Solution
一眼看出概率 dp，但如何似乎没思路？开始公式做题：设置状态+推转移式。
\(Q1\)：怎么设置状态？
首先，思考一个问题：第 \(k\) 个人该怎么“赢”呢？
我们称前4人的比赛为“擂台”，一场擂台只会有一个胜者，这位胜者被称为“擂主”，再称那第 \(k\) 位选手为勇者。
勇者要赢，首先要等待再等待，进入“擂台”，并且保持胜利直至连胜 \(m\) 场，期间若输了则要再继续进行上述操作直到连胜 \(m\) 场。
那么，勇者要赢，首先要进入擂台，那么在他进入擂台前，擂主不能连赢大于等于 \(m\) 场，所以有一维状态 \(j\)，表示擂主连胜了 \(j\) 场。
其次，他要在擂台上连赢 \(m\) 场，若输了，就要到最后排队，这时候勇者的位置会发生变化，所以另一维状态 \(i\)，表示勇者在第 \(i\) 的位置。
那么 dp 的状态设置就很明了了，\(f_{i,j}\) 表示勇者在第 \(i\) 的位置，擂主已连胜 \(j\) 场时赢的概率。
\(Q2\)：怎么推转移式？
对于 \(i\) 的值分类讨论。
边界条件（连胜了 \(m\) 场）
\(f_{1,m} = 1\)，其他都是 \(0\)。因为只有自己是擂主时才能赢。
自己是擂主（\(i = 1\)）
\(f_{1, j} = \frac{1}{4} \times f_{1, j + 1} + \frac{3}{4} \times f_{n - 2, 1}\)。自己胜了就胜场 \(+1\)；反之掉到 \(n-2\) 的位置，胜场变为 \(1\)。
入了擂台，但不是擂主（\(1 < i \le 4\)）
\[ f_{i, j} = \begin{cases} \frac{1}{4} \times f_{1, 1} + \frac{1}{4} \times f_{n - 2, j + 1} + \frac{1}{4} \times f_{n - 1, 1} + \frac{1}{4} \times f_{n, 1} & i = 2 \\ \frac{1}{4} \times f_{1, 1} + \frac{1}{4} \times f_{n - 1, j + 1} + \frac{1}{4} \times f_{n - 1, 1} + \frac{1}{4} \times f_{n, 1} & i = 3 \\ \frac{1}{4} \times f_{1, 1} + \frac{1}{4} \times f_{n - 1, j + 1} + \frac{1}{2} \times f_{n, 1} & i = 4 \end{cases} \]对于各个位置分开讨论。
在等待入擂台的队伍中（\(i > 4\)）
\(f_{i, j} = \frac{1}{4} \times f_{i - 3, j + 1} + \frac{3}{4} \times f_{i - 3, 1}\)。只看当前擂主是否胜利。
收尾
dp 式子有依赖关系怎么办？
没事，\(n \times (m+1)\) 只有 \(100\) 的量级，\(O(n^3m^3)\) 可过。
所以高斯消元即可。复杂度 \(O(n^3m^3)\)（还有 \(O(n^2m + m^3)\) 做法但我不会，不做讲解）。
另外，本题还能打表。
Code
// 高斯消元
// written by Naught
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;
#define Maxn 15
#define Maxm 105
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define fr(i, r, l) for (int i = l; i >= r; --i)
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
inline ll lread(ll x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
inline void train() {ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);}
lb f[Maxn][Maxn][Maxn], a[Maxm][Maxm];
int pos_in_Matrix(int x, int y, int m) {return (x - 1) * (m + 1) + y;}
void gauss(int x)
{
fo(i, 0, x - 1)
{
int row = i;
fo(j, i, x - 1) if(fabs(a[row][i]) < fabs(a[j][i])) row = j;
if(row != i) swap(a[row], a[i]);
lb res = a[i][i];
fo(j, 0, x) a[i][j] /= res;
fo(j, i + 1, x - 1)
{
res = a[j][i];
fo(k, 0, x) a[j][k] -= a[i][k] * res;
}
}
fr(i, 0, x - 1) fr(j, 0, i - 1) a[j][x] -= a[j][i] * a[i][x], a[j][i] = 0;
}
lb Solve(int n, int m, int k)
{
int upper = n * (m + 1), p = 0;
memset(a, 0, sizeof(a));
a[p][pos_in_Matrix(1, m, m)] += 1, a[p][upper] += 1, ++p;
fo(i, 2, n) a[p][pos_in_Matrix(i, m, m)] += 1, ++p;
fo(j, 0, m-1) a[p][pos_in_Matrix(1, j, m)] += 1, a[p][pos_in_Matrix(1, j + 1, m)] -= 0.25, a[p][pos_in_Matrix(n - 2, 1, m)] -= 0.75, ++p;
fo(j, 0, m-1) a[p][pos_in_Matrix(2, j, m)] += 1, a[p][pos_in_Matrix(1, 1, m)] -= 0.25, a[p][pos_in_Matrix(n - 2, j + 1, m)] -= 0.25, a[p][pos_in_Matrix(n - 1, 1, m)] -= 0.5, ++p;
fo(j, 0, m-1) a[p][pos_in_Matrix(3, j, m)] += 1, a[p][pos_in_Matrix(1, 1, m)] -= 0.25, a[p][pos_in_Matrix(n - 1, j + 1, m)] -= 0.25, a[p][pos_in_Matrix(n - 1, 1, m)] -= 0.25, a[p][pos_in_Matrix(n, 1, m)] -= 0.25, ++p;
fo(j, 0, m-1) a[p][pos_in_Matrix(4, j, m)] += 1, a[p][pos_in_Matrix(1, 1, m)] -= 0.25, a[p][pos_in_Matrix(n, j + 1, m)] -= 0.25, a[p][pos_in_Matrix(n, 1, m)] -= 0.5, ++p;
fo(i, 5, n) fo(j, 0, m-1) a[p][pos_in_Matrix(i, j, m)] += 1, a[p][pos_in_Matrix(i - 3, j + 1, m)] -= 0.25, a[p][pos_in_Matrix(i - 3, 1, m)] -= 0.75, ++p;
gauss(upper);
return a[pos_in_Matrix(k, 0, m)][upper];
}
int main()
{
int _ = read(), n = read(), m = read(), k = read();
printf("%.6Lf", Solve(n, m, k));
return 0;
}
// 打表
// written by Naught
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;
#define Maxn 15
#define fo(i, l, r) for (ll i = l; i <= r; ++i)
#define fr(i, r, l) for (int i = l; i >= r; --i)
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
inline ll lread(ll x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
inline void train() {ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);}
lb f[Maxn][Maxn][Maxn] = {
{
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000}
},
{
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000}
},
{
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000}
},
{
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000}
},
{
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.217626 ,0.214029 ,0.205036 ,0.190647 ,0.172662 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.204447 ,0.202897 ,0.200883 ,0.198404 ,0.193368 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.201020 ,0.200713 ,0.200250 ,0.199631 ,0.198388 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.200258 ,0.200180 ,0.200063 ,0.199907 ,0.199593 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.200064 ,0.200045 ,0.200016 ,0.199977 ,0.199898 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.200016 ,0.200011 ,0.200004 ,0.199994 ,0.199975 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.200004 ,0.200003 ,0.200001 ,0.199999 ,0.199994 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.200001 ,0.200001 ,0.200000 ,0.200000 ,0.199998 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.200000 ,0.200000 ,0.200000 ,0.200000 ,0.200000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000}
},
{
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.196429 ,0.178571 ,0.169643 ,0.169643 ,0.142857 ,0.142857 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.172295 ,0.169859 ,0.168180 ,0.167258 ,0.162357 ,0.160051 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.168119 ,0.167476 ,0.167036 ,0.166797 ,0.165505 ,0.165066 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.167028 ,0.166865 ,0.166757 ,0.166703 ,0.166378 ,0.166270 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.166757 ,0.166716 ,0.166689 ,0.166676 ,0.166594 ,0.166567 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.166689 ,0.166679 ,0.166672 ,0.166669 ,0.166649 ,0.166642 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.166672 ,0.166670 ,0.166668 ,0.166667 ,0.166662 ,0.166660 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.166668 ,0.166667 ,0.166667 ,0.166667 ,0.166666 ,0.166665 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.166667 ,0.166667 ,0.166667 ,0.166667 ,0.166666 ,0.166666 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
},
{
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.153226 ,0.153226 ,0.153226 ,0.153226 ,0.129032 ,0.129032 ,0.129032 ,0.000000 ,0.000000 ,0.000000},
{0.145879 ,0.145879 ,0.145879 ,0.145879 ,0.138829 ,0.138829 ,0.138829 ,0.000000 ,0.000000 ,0.000000},
{0.143570 ,0.143570 ,0.143570 ,0.143570 ,0.141907 ,0.141907 ,0.141907 ,0.000000 ,0.000000 ,0.000000},
{0.143037 ,0.143037 ,0.143037 ,0.143037 ,0.142617 ,0.142617 ,0.142617 ,0.000000 ,0.000000 ,0.000000},
{0.142902 ,0.142902 ,0.142902 ,0.142902 ,0.142797 ,0.142797 ,0.142797 ,0.000000 ,0.000000 ,0.000000},
{0.142868 ,0.142868 ,0.142868 ,0.142868 ,0.142842 ,0.142842 ,0.142842 ,0.000000 ,0.000000 ,0.000000},
{0.142860 ,0.142860 ,0.142860 ,0.142860 ,0.142853 ,0.142853 ,0.142853 ,0.000000 ,0.000000 ,0.000000},
{0.142858 ,0.142858 ,0.142858 ,0.142858 ,0.142856 ,0.142856 ,0.142856 ,0.000000 ,0.000000 ,0.000000},
{0.142857 ,0.142857 ,0.142857 ,0.142857 ,0.142857 ,0.142857 ,0.142857 ,0.000000 ,0.000000 ,0.000000}
},
{
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.144964 ,0.143412 ,0.138496 ,0.130217 ,0.121421 ,0.117282 ,0.113142 ,0.091066 ,0.000000 ,0.000000},
{0.130480 ,0.129798 ,0.128514 ,0.126629 ,0.123567 ,0.122343 ,0.120837 ,0.117833 ,0.000000 ,0.000000},
{0.126337 ,0.126133 ,0.125840 ,0.125455 ,0.124681 ,0.124396 ,0.123965 ,0.123193 ,0.000000 ,0.000000},
{0.125334 ,0.125284 ,0.125210 ,0.125113 ,0.124917 ,0.124844 ,0.124747 ,0.124551 ,0.000000 ,0.000000},
{0.125083 ,0.125071 ,0.125053 ,0.125028 ,0.124979 ,0.124961 ,0.124937 ,0.124888 ,0.000000 ,0.000000},
{0.125021 ,0.125018 ,0.125013 ,0.125007 ,0.124995 ,0.124990 ,0.124984 ,0.124972 ,0.000000 ,0.000000},
{0.125005 ,0.125004 ,0.125003 ,0.125002 ,0.124999 ,0.124998 ,0.124996 ,0.124993 ,0.000000 ,0.000000},
{0.125001 ,0.125001 ,0.125001 ,0.125000 ,0.125000 ,0.124999 ,0.124999 ,0.124998 ,0.000000 ,0.000000},
{0.125000 ,0.125000 ,0.125000 ,0.125000 ,0.125000 ,0.125000 ,0.125000 ,0.125000 ,0.000000 ,0.000000}
},
{
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.138514 ,0.128378 ,0.123311 ,0.123311 ,0.108108 ,0.108108 ,0.108108 ,0.081081 ,0.081081 ,0.000000},
{0.118047 ,0.115746 ,0.114416 ,0.114059 ,0.110159 ,0.109253 ,0.108938 ,0.105053 ,0.104328 ,0.000000},
{0.112697 ,0.112275 ,0.111989 ,0.111841 ,0.110993 ,0.110662 ,0.110514 ,0.109668 ,0.109361 ,0.000000},
{0.111508 ,0.111400 ,0.111328 ,0.111291 ,0.111075 ,0.111003 ,0.110967 ,0.110751 ,0.110676 ,0.000000},
{0.111211 ,0.111184 ,0.111165 ,0.111156 ,0.111102 ,0.111084 ,0.111075 ,0.111021 ,0.111003 ,0.000000},
{0.111136 ,0.111129 ,0.111125 ,0.111122 ,0.111109 ,0.111104 ,0.111102 ,0.111089 ,0.111084 ,0.000000},
{0.111117 ,0.111116 ,0.111115 ,0.111114 ,0.111111 ,0.111109 ,0.111109 ,0.111105 ,0.111104 ,0.000000},
{0.111113 ,0.111112 ,0.111112 ,0.111112 ,0.111111 ,0.111111 ,0.111111 ,0.111110 ,0.111109 ,0.000000},
{0.111111 ,0.111111 ,0.111111 ,0.111111 ,0.111111 ,0.111111 ,0.111111 ,0.111111 ,0.111111 ,0.000000}
},
{
{0.250000 ,0.250000 ,0.250000 ,0.250000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000},
{0.116242 ,0.116242 ,0.116242 ,0.116242 ,0.101911 ,0.101911 ,0.101911 ,0.076433 ,0.076433 ,0.076433},
{0.104134 ,0.104134 ,0.104134 ,0.104134 ,0.099471 ,0.099471 ,0.099471 ,0.095017 ,0.095017 ,0.095017},
{0.101070 ,0.101070 ,0.101070 ,0.101070 ,0.099872 ,0.099872 ,0.099872 ,0.098701 ,0.098701 ,0.098701},
{0.100264 ,0.100264 ,0.100264 ,0.100264 ,0.099972 ,0.099972 ,0.099972 ,0.099677 ,0.099677 ,0.099677},
{0.100066 ,0.100066 ,0.100066 ,0.100066 ,0.099993 ,0.099993 ,0.099993 ,0.099919 ,0.099919 ,0.099919},
{0.100016 ,0.100016 ,0.100016 ,0.100016 ,0.099998 ,0.099998 ,0.099998 ,0.099980 ,0.099980 ,0.099980},
{0.100004 ,0.100004 ,0.100004 ,0.100004 ,0.100000 ,0.100000 ,0.100000 ,0.099995 ,0.099995 ,0.099995},
{0.100001 ,0.100001 ,0.100001 ,0.100001 ,0.100000 ,0.100000 ,0.100000 ,0.099999 ,0.099999 ,0.099999},
{0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000 ,0.000000}
}
};
int main()
{
int _ = read(), n = read()-1, m = read()-1, k = read()-1;
printf("%.6Lf", f[n][m][k]);
return 0;
}