← Home
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

type ext struct {
	m float64
	e int32
}

func main() {
	var n int
	var X int

	in := bufio.NewReader(os.Stdin)
	if _, err := fmt.Fscan(in, &n, &X); err != nil {
		return
	}

	c := float64(X) / 1000000.0

	pr := make([]int, n+1)
	for i := 0; i <= n; i++ {
		fmt.Fscan(in, &pr[i])
	}

	lfact := make([]float64, n+1)
	for i := 1; i <= n; i++ {
		lfact[i] = lfact[i-1] + math.Log2(float64(i))
	}

	p := make([]ext, n+1)
	for r := 0; r <= n; r++ {
		if pr[r] == 0 {
			p[r] = ext{0.0, 0}
		} else {
			log2Comb := lfact[n] - lfact[r] - lfact[n-r]
			L := math.Log2(float64(pr[r])/1000000.0) - log2Comb
			e := int32(math.Floor(L)) + 1
			m := math.Exp2(L - float64(e))
			p[r] = ext{m, e}
		}
	}

	var pow2 [60]float64
	for i := 0; i < 60; i++ {
		pow2[i] = math.Exp2(float64(-i))
	}

	V := make([]float64, n+1)
	nextV := make([]float64, n+1)
	nextPArr := make([]ext, n+1)

	for d := n - 1; d >= 0; d-- {
		for r := 0; r <= d; r++ {
			a := p[r]
			b := p[r+1]

			var nextP ext
			if a.m == 0 {
				nextP = b
			} else if b.m == 0 {
				nextP = a
			} else {
				var diffE int32
				if a.e >= b.e {
					diffE = a.e - b.e
					if diffE > 59 {
						nextP = a
					} else {
						m := a.m + b.m*pow2[diffE]
						if m >= 1.0 {
							nextP = ext{m * 0.5, a.e + 1}
						} else {
							nextP = ext{m, a.e}
						}
					}
				} else {
					diffE = b.e - a.e
					if diffE > 59 {
						nextP = b
					} else {
						m := b.m + a.m*pow2[diffE]
						if m >= 1.0 {
							nextP = ext{m * 0.5, b.e + 1}
						} else {
							nextP = ext{m, b.e}
						}
					}
				}
			}

			if nextP.m == 0 {
				nextV[r] = 0.0
			} else {
				var probRed float64
				if b.m == 0 {
					probRed = 0.0
				} else {
					diff := nextP.e - b.e
					if diff > 59 {
						probRed = 0.0
					} else {
						probRed = (b.m / nextP.m) * pow2[diff]
					}
				}
				if probRed > 1.0 {
					probRed = 1.0
				}

				expected := -c + probRed*(1.0+V[r+1]) + (1.0-probRed)*V[r]
				if expected > 0.0 {
					nextV[r] = expected
				} else {
					nextV[r] = 0.0
				}
			}
			nextPArr[r] = nextP
		}

		p, nextPArr = nextPArr, p
		V, nextV = nextV, V
	}

	fmt.Printf("%.12f\n", V[0])
}