飞行棋

Time Limit: 16000/8000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

九爷在玩一种新型的飞行棋,规则很简单,有N(2<=N<=100000)个格子,编号为1到N,从结点1出发,当恰好到达结点N的时候结束。每到一个格子,都会使用一种独特的骰子来决定移动到哪一步。骰子是由5个面组成的,分别对应-2、-1、0、1、2。如果当前在格子i,当骰子结果是-2时,会到达格子i-2,-1时到达格子i-1,0时留在格子i,1时到达格子i+1,2时到达i+2。但是在两个端点处,就是格子1左边和格子N右边,相当于有反射壁,如在格子1遇到-1会到格子1,遇到-2会到格子2,在格子N遇到1会到格子N,遇到2会到格子N-1。

从格子1出发,每步摇一次骰子,走相应的步数,停在格子N时候结束。需要求操作步数的期望。

每个格子对应的骰子是不一样的,就是5个面出现的概率不同。在格子i,-2、-1、0、1、2出现的概率分别为p1、p2、p3、p4、p5。

对于格子i会有五个对应的正整数ai、bi、ci、di、ei(1<=ai<=bi<=ci<=di<=ei<=10),则该点对应的五个概率为p1=ai/(ai+bi+ci+di+ei)、p2=bi/(ai+bi+ci+di+ei)、p3=ci/(ai+bi+ci+di+ei)、p4=di/(ai+bi+ci+di+ei)、p5=ei/(ai+bi+ci+di+ei)

Input

多组输入。

每组输入第一行一个整数N(2<=N<=100000)

接下来N行,每行5个正整数ai、bi、ci、di、ei(1<=ai<=bi<=ci<=di<=ei<=10)。

Output

输出需要的操作步数的期望值,精确到两位小数。

Sample Input

2
1 1 1 1 1
1 1 1 1 1

Sample Output

1.67

Source

kuangbin

Manager

Information
Solved Number18
Submit Number56
Problem Tags
probabilities
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel