utkarsh-and-jumps

Utkarsh being a very talkative child, was scolded by his teacher multiple times. One day, the teacher became very angry and decided to give him a very rigorous punishment. He made him stand on the school field which is X axis. 

Utkarsh initially stood at X = 0. The teacher asked him to run to X = N.  But, to make the process quick, Utkarsh decided that he will make jumps of 2 or 3 steps only, i.e., from X = S he can jump to X = S+2 or X = S+3.

Utkarsh decided that he will jump 2 steps with probability P/100 and jump 3 steps with probability 1-P/100.

You need to find the probability that he will reach exactly on X = N.  

Constraints:
0 < N ≤ 10^6  
0 ≤ P ≤ 100  

Input Constraints:
The first line contains two integer N and P.  

Output Constraints:
Your answer must contain exactly 6 digits after the decimal point.

SAMPLE INPUT
5 20

SAMPLE OUTPUT
0.320000

Explanation

There are two ways to reach 5.

2+3 with probability =0.2 * 0.8=0.16

3+2 with probability =0.8 * 0.2=0.16

So, total probability = 0.32.

Difficulty: EASY
Tags: Dynamic programming

Probability
Skill types: Dynamic programming

Starter code:

Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''


N, P = list(map(int, input().split()))
Prob = []
Prob.append(0)
Prob.append(0)
Prob.append(P/100)
Prob.append(1 - Prob[2])
for i in range(4,N+1):
	Prob.append(Prob[i-2]*Prob[2] + Prob[i-3]*Prob[3])
			
print("%.6f" %Prob[N])



n,p = list(map(int,input().split()))

p = p/100.0
#print(p)
tp = [0]*(n+1)
if(n==1):
	print((0))
elif(n==2):
	print(("%.6f" % p))
elif(n==3):
	t = 1-p
	print(("%.6f" % t))
else:
	tp[1] = 0
	tp[2] = p
	tp[3] = 1-p
	for i in range(4,n+1):
		tp[i] = tp[i-3]*(1-p) + tp[i-2]*(p)
	#t = tp[n]
	print(("%.6f" % tp[n]))



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
steps = [2,3]
n,p =  input().split(' ')
n = int(n)
p = float(p)
probability = [0.0 for i in range(0,n+1)]
probability[2] = p/100
probability[3] = 1-(p/100)
for i in range(4,n+1):
	if(probability[i-2]>0):
		probability[i]=probability[i]+(probability[i-2]*probability[2])
	if(probability[i-3]>0):
		probability[i]=probability[i]+(probability[i-3]*probability[3])

print(("%.6f" %probability[n]))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
 

NP = input('')
N = int(NP.split()[0])
P=  int(NP.split()[1])

#print P,N
ans=0.0000
ways=[]
ways.append('')#0
ways.append(0.0000)#1
ways.append((P)/100.0)#2
ways.append((100-P)/100.0)#3
ways.append((P/100.0)*(P/100.0))#4

for i in range(5,N+1):
	a=ways[i-2]*(P/100.0)
	b=ways[i-3]*((100-P)/100.0)
	ways.append(a+b)

print("{0:.6f}".format(ways[N]))
	


n,p=list(map(int,input().split()))
p=p/100.0
dp=[-1]*(n+1)
dp[0]=1
dp[1]=0
dp[2]=p
dp[3]=1-p
for i in range(4,n+1):
	dp[i]=dp[i-2]*p+dp[i-3]*(1-p)
print("%.6f"%dp[n])    


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

N, P = list(map(int, input().split()))

Prob = [None]*(N+1)
Prob[0] = Prob[1] = 0
Prob[2] = P/100
Prob[3] = 1 - Prob[2]

for i in range(4,N+1):
	Prob[i] = Prob[i-2]*Prob[2] + Prob[i-3]*Prob[3]

print("%.6f" %Prob[N])



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''


N, P = list(map(int, input().split()))

def probability(n,p):
	Prob = [None]*(n+1)
	Prob[0] = Prob[1] = 0
	Prob[2] = p/100
	Prob[3] = 1 - Prob[2]
	

	for i in range(4,n+1):
	    Prob[i] = Prob[i-2]*Prob[2] + Prob[i-3]*Prob[3]
	    

	print("%.6f" %Prob[n])

probability(N,P)


 
NP=input().split()
N=int(NP[0])
P=int(NP[1])
P2=P/100
P3=1-P2
Cache={0:1,1:0,2:P2,3:P3}
for i in range(4,N+1):
	Cache[i]=Cache[i-2]*P2+Cache[i-3]*P3
print('%.6f' %Cache[N])



def prob(n,p1,p2):
	mem=[0 for i in range(n+3)]
	mem[0]=0.0
	mem[1]=0.0
	mem[2]=p1
	mem[3]=p2
	for i in range(4,n+1):
		mem[i]=p1*mem[i-2]+p2*mem[i-3]
	return mem[n]

inp=[int(i) for i in input().split(" ")]
p1=inp[1]/100.0
p2=1-p1

print("%.6f"%prob(inp[0],p1,p2))


n,p=list(map(int,input().split()))
#print n,p
dp={}
dp[0]=0
dp[1]=0
two=p/100.0
three=(100-p)/100.0
#print two,three
dp[2]=two
dp[3]=three
for i in range(4,n+1):
	#print("%d : %.6f  +  %.6f"%(i,dp[i-2],dp[i-3]))
	dp[i]=(dp[i-2]*two)+(dp[i-3]*three)

print("%.6f"%dp[n])



n,m = list(map(int,input().split()))
a = [0 for i in range(n+1)]
p = float(m)/100
a[0] = 1
a[2] = p
for i in range(3,n+1):
	a[i] = a[i]+a[i-2]*p+a[i-3]*(1-p)
	
print("%.6f" % a[n])


s = input()
s = s.split(' ')
n = int(s[0])
p = float(s[1])

steps = []
steps.append(0)
steps.append(0)

p2=float(p/100)
p3=float(1-p2)

#print p2, p3

steps.append(p2)
steps.append(p3)
i=4
while i<=n:
	steps.append((steps[i-2]*p2) + (steps[i-3]*p3))
	i+=1
print("%0.6f"%steps[n])


n,p=list(map(int,input().split()))
#print n,p
dp={}
dp[0]=0
dp[1]=0
two=p/100.0
three=(100-p)/100.0
#print two,three
dp[2]=two
dp[3]=three
for i in range(4,n+1):
	#print("%d : %.6f  +  %.6f"%(i,dp[i-2],dp[i-3]))
	dp[i]=(dp[i-2]*two)+(dp[i-3]*three)

print("%.6f"%dp[n])



N,P = [int(x) for x in input().split()]
parr = [-1]*(N+1)
p2     = P/100.0
p3     = 1-p2
parr[0]=1
parr[1]=0
parr[2]=p2 
for i in range(3,N+1):
	parr[i] = parr[i-2]*p2+parr[i-3]*p3
 
print("%.6f" % parr[N])


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import math
N,p=list(map(int,input().split()))
ip = p/100.0;
total_probability = 0;
 
steps = {0:1, 1:0, 2:ip, 3:(1-ip)};
 
for i in range(3,N+1):
	steps[i] = (steps[i-2]*ip + steps[i-3]*(1-ip));
	
print("{:0.6f}".format(steps[N]));



n,p = list(map(int,input().split()))
p = float(p)
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 0
dp[2] = p/100
dp[3] = 1-p/100
for i in range(4,n+1):
	dp[i] = (p/100) * dp[i-2] + (1-p/100) * dp[i-3]
print("%.6f"%dp[n])