黑白棋游戏

时间限制:10s      空间限制:128MB

题目描述

黑白棋游戏是这样玩的:首先GEN随机生成N01序列,0表示白棋,1表示黑棋。接着两个人轮流按如下规则取棋:首先选取一个非空的01序列,然后从该序列的左边开始连续取若干个棋子,这些被取的棋子中最多只能有一个黑棋,且该黑棋必需恰好是连续取的最后一个棋子,比如当前的序列为001001,则可以取走的棋子有三种情况,分别为:000001。如果某人没有棋子可取了,则他负。

你通过特殊手段得到了GEN生成时每一行生成的白棋数目和黑棋数目,由于不知道它们的排列情况,你做不到必胜,你只想知道你先手获胜的概率有多大(假设你和你的对手都无限聪明)


输入格式

 

第一行一个数N

第二行N个数,第i个数表示第i01序列中黑棋的个数。

第三行N个数,第i个数表示第i01序列中白棋的个数。


输出格式

仅一行,一个保留6为小数的的实数表示先手获胜的概率。


样例输入

1

1

1



样例输出

0.500000

提示


样例解释

若生成序列为01,则先手必胜;若生成序列为10,则后手必胜。

两种情况出现的概率均为0.5,故先手获胜的概率为0.5。

0<=每行的黑棋个数<=100

0<=每行的白棋个数<=100

1<=N<=50

数据保证每个序列至少有一个棋子。


题目来源

没有写明来源