Google Code Jam 2012 Round 1A Problem A. Password Problem

Password Problem

k文字目まで全部正解している確率P[k]は、P[k]=Π_i=1^kp_i。x回バックスペースを押したとき、それ以前の場所が全て正解していればキーストロークは2x+B-A+1回、そうでなければ2x+B-A+1+B+1回。諦めたときはB+2回。

for test in range(input()):
    A,B = map(int,raw_input().split())
    p = map(float,raw_input().split())
    P = [1]
    for i in xrange(A):
        P += [P[i]*p[i]]
    ans = min([(2*i+B-A+1)+(1-P[-i-1])*(B+1)for i in range(A+1)]+[B+2])
    print "Case #%d: %.20f"%(test+1,ans)