UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2319. 黑白棋游戏

Statistics 下载数据

Description

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

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

Input

 

第一行一个数N

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

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

Output

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

Sample Input

1

1

1


Sample Output

0.500000

Hint




样例解释


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


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


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


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


1<=N<=50


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

Source