Problem:


Sleeping Time

Miki is a high school student.
She has  a part time job, so she cannot take enough sleep  on weekdays.
She wants to take good sleep  on holidays, but she doesn't know  the  best length of sleeping time for her.

She is now trying to figure that out with the following algorithm:

 Begin with the numbers K, R and L.

She  tries to sleep for H=(R+L)/2 hours.

If she feels  the time is longer than or equal to the optimal length, then  update L with H.  Otherwise,  update R with H.

After repeating step 2 and  3 for K  nights, she decides her optimal sleeping time to be T' = (R+L)/2.

If her feeling  is always correct,  the steps described above should give her a very accurate optimal sleeping time.
But unfortunately, she makes mistake in step 3  with the probability P.

 Assume you know  the optimal sleeping time T for Miki.
You have to calculate the probability PP that the absolute difference of T' and T is  smaller or equal to E.
It is guaranteed that the answer remains unaffected  by the change of E in 10^{-10}.

Input

The input follows the format shown below

 K R L

 P

 E

 T

Where the integers  0 \leq K \leq 30, 0 \leq R \leq L \leq 12 are the parameters for the algorithm described above.
 The decimal numbers on the following three lines of the input gives the parameters for the estimation.  You can assume 0 \leq P \leq 1, 0 \leq E \leq 12, 0 \leq T \leq 12.

Output

Output PP in one line.

The output should not contain an error greater than 10^{-5}.

Sample Input 1

3 0 2
0.10000000000
0.50000000000
1.00000000000

Output for the Sample Input 1

0.900000

Sample Input 2

3 0 2
0.10000000000
0.37499999977
1.00000000000

Output for the Sample Input 2

0.810000

Sample Input 3

3 0 2
0.10000000000
0.00000100000
0.37500000000

Output for the Sample Input 3

0.729000

Sample Input 4

3 0 2
0.20000000000
0.00000100000
0.37500000000

Output for the Sample Input 4

0.512000



Sample input:
3 0 2
0.10000000000
0.50000000000
1.00000000000


Sample output:
0.900000

Submission status: Wrong Answer

Solution code:
K,R,L = map(int,raw_input().split())
P = float(raw_input())
E = float(raw_input())
T = float(raw_input())

def rec(r,l,k):
    if T-E <= r <= l <= T+E: return 1.0
    if T+E <= r or l <= T-E or k == 0: return 0.0
    h = (r+l)/2.0
    if h >= T:
        return (1-P)*rec(r,h,k-1)+P*rec(h,l,k-1)
    else:
        return (1-P)*rec(h,l,k-1)+P*rec(r,h,k-1)

print "%.10f"%rec(R,L,K)

Submission status: Wrong Answer

Solution code:
K,R,L = map(int,raw_input().split())
P = float(raw_input())
E = float(raw_input())
T = float(raw_input())

def rec(r,l,k):
    h = (r+l)/2.0
    if T-E <= h <= T+E: return 1.0
    if T+E <= r or l <= T-E or k == 0: return 0.0
    if h >= T:
        return (1-P)*rec(r,h,k-1)+P*rec(h,l,k-1)
    else:
        return (1-P)*rec(h,l,k-1)+P*rec(r,h,k-1)

print "%.10f"%rec(R,L,K)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    k,r,l = LI()
    p = F()
    e = F()
    t = F()

    def f(k,r,l):
        if abs(r-t) <= e and abs(t-l) <= e:
            return 1
        if t-l > e or r-t > e:
            return 0
        if k == 0:
            if abs(t - (r+l) / 2) <= e:
                return 1
            return 0

        h = (r+l) / 2
        if h >= t:
            return f(k-1,r,h) * (1-p) + f(k-1,h,l) * p
        return f(k-1,r,h) * p + f(k-1,h,l) * (1-p)

    tr = f(k,r,l)

    return '{:0.9f}'.format(tr)



print(main())

Submission status: Accepted

Solution code:
K,R,L = map(int,raw_input().split())
P = float(raw_input())
E = float(raw_input())
T = float(raw_input())

def rec(r,l,k):
    h = (r+l)/2.0
    if k == 0:
        return 1.0 if T-E <= h <= T+E else 0.0
    if T-E <= r and l <= T+E: return 1.0
    if T+E <= r or l <= T-E: return 0.0

    if h >= T:
        return (1-P)*rec(r,h,k-1)+P*rec(h,l,k-1)
    else:
        return (1-P)*rec(h,l,k-1)+P*rec(r,h,k-1)

print "%.10f"%rec(R,L,K)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def input():
	return sys.stdin.readline()[:-1]

EPS = 1e-10
k, L, R = map(int, input().split())
p = float(input())
e = float(input())
t = float(input())

def search(l, r, prob, depth):
	#print(l, r, prob, depth) 
	if depth == k:
		h = (l+r)/2
		if abs(h-t) + EPS < e:
			return prob
		else:
			return 0
	else:
		if l - EPS > t + e or r + EPS < t - e:
			return 0
		elif l + EPS > t - e and t + e > r - EPS:
			return prob
		else:
			h = (l+r)/2
			if h >= t:
				return search(h, r, prob * p, depth+1) + search(l, h, prob * (1-p), depth+1)
			else:
				return search(h, r, prob * (1-p), depth+1) + search(l, h, prob * p, depth+1)

ans = search(L, R, 1, 0)
print('{:.12f}'.format(ans))

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    k,r,l = LI()
    p = F()
    e = F()
    t = F()

    def f(k,r,l):
        if abs(r-t) <= e and abs(t-l) <= e:
            return 1
        if k == 0:
            if abs(t - (r+l) / 2) <= e:
                return 1
            return 0

        h = (r+l) / 2
        if h >= t:
            return f(k-1,r,h) * (1-p) + f(k-1,h,l) * p
        return f(k-1,r,h) * p + f(k-1,h,l) * (1-p)

    tr = f(k,r,l)

    return '{:0.9f}'.format(tr)



print(main())