[AGC019F] Yes or No

将答案序列看作一条平面上由 $(n,m)$ 到 $(0,0)$ 的路径，某次答案为 Yes 则往左走，否则往下走。于是每道题都与某条边一一对应；而每次答题人所面对的状态，即目前两种答案分别剩 $x,y$ 个，则与平面上某个点 $(x,y)$ 一一对应。

那么答题人的最优策略是显然的，当目前在直线 $y=x$ 以下时，猜答案为 Yes；当目前在直线 $y=x$ 以上时，猜答案为 No；当恰好落在直线上时，随便怎么猜，猜对的概率均为 $\frac12$。

我们来考察某种答案序列所对应的路径，假设 $n\ge m$，将整条路径在所有 $x=y$ 点处断开，形成多个段。

$n>m$ 时第一个段一定在 $y=x$ 下，这个段中每次询问都会得到回答 Yes，其中所有向左走的路径对应的问题是正确的，于是这段中答对问题的数量等于这部分路径的 $x$ 坐标跨度。

其余段中，除了段首第一个询问恒定有 $\frac12$ 的概率是正确的，其余所有边朝向直线 $y=x$ 的问题都是回答正确的。而这些段中起点终点均在 $y=x$ 上，所以 $x$ 坐标跨度等于 $y$ 坐标跨度，所以这些段中回答正确的问题数量期望都等于 $x$ 坐标跨度加 $\frac12$。

于是总答案等于 $n+\frac k2$，其中 $k$ 为回答的第二类段的期望数量，等于该路径与直线 $y=x$ 的交点个数减一。

那么对于每个点 $(x,x)$ 计算路径经过它的概率，计算相应贡献即可。