ikshus-love-for-binary-numbers

Ikshu's love for binary numbers

Ikshu recently learnt to generate random numbers. He is generating stream binary numbers. Uptil now he has generated N bits of the binary number. Now, he wants to know if there is a streak of contiguous 1's of length K.

Help him to find the probability of existence of such a streak in his binary number.

Assume that probability of generating a one and zero is equal i.e 0.5.

Input:
First and only line of input contains two space separated integers N and K as described above.

Output:
output contains one line containing probablity. output should be in n/m form where it is n/m is in its lowest fraction.

Constraints:
1 ≤ N ≤ 60
1 ≤ K ≤ N

SAMPLE INPUT
5 1

SAMPLE OUTPUT
31/32

Explanation

Ikshu generated the 5 BIT binary number. Now, Out of 32 distinct binary numbers possible there are 31 cases having atleast one set bit. So, ans is 31/32

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import sys


def compute(mat, n, k):
	for i in range(1, n + 1):
		for j in range(k + 1):
			if j == 1:
				mat[i][j] = pow(2, i) - 1
				continue
			if i - j - 1 >= 0:
				mat[i][j] = 2 * mat[i - 1][j] + (pow(2, i - j - 1) - mat[i - j - 1][j])
			elif i - j == 0:
				mat[i][j] = 1

def main():
	n, k = [int(tok) for tok in sys.stdin.readline().split()]
	mat = [[0 for i in range(k + 1)] for i in range(n + 1)]
	compute(mat, n, k)
	num = mat[n][k]
	denom = pow(2, n)
	while (num & 0x1 == 0):
		num >>= 1
		denom >>= 1
	print(("%d/%d" % (num, denom)))

if __name__ == "__main__":
	main()




n, k = list(map(int, input().strip().split()))

array = [0 for _ in range(k)]
array.append(1)

powers = [2 ** i for i in range(n+1)]

for i in range(k+1, n+1):
	array.append(powers[i - k - 1] - array[i - k - 1] + 2 * array[i-1])

num = array[-1]
denom = powers[-1]

while num % 2 == 0:
	num = int(num / 2)
	denom = int(denom / 2)

print("%d/%d" % (num, denom))


from fractions import Fraction

n, k = list(map(int, input().split()))
dp = [1] + [0] * (k - 1)
for _ in range(n):
	dp = [sum(dp)] + dp[:-1]
	
bad = sum(dp)
total = 1 << n
good = total - bad
print(Fraction(good, total))


import sys

for line in sys.stdin:
	if len(line) > 1:
		(n, k) = list(map(int, line.split()))
		s = [0]*(n+1)
		s[k] = 1 # T(k, k) = 1
		for i in range(k + 1, n + 1):
			s[i] = 2*s[i-1] + pow(2, (i - k - 1)) - s[i-1-k]
		a = s[n]    
		b = pow(2, n)
		while (a % 2 == 0):
			a = a/2
			b = b/2
		print("%d%c%d" % (a, '/', b))
	


import sys

for line in sys.stdin:
	if len(line) > 1:
		(n, k) = list(map(int, line.split()))
		s = [0]*(n+1)
		s[k] = 1 # T(k, k) = 1
		for i in range(k + 1, n + 1):
			s[i] = 2*s[i-1] + pow(2, (i - k - 1)) - s[i-1-k]
		a = s[n]    
		b = pow(2, n)
		while (a % 2 == 0):
			a = a/2
			b = b/2
		print("%d%c%d" % (a, '/', b))
	


from fractions import gcd
def simp(a, b):
	x = gcd(a, b)
	return (str(a//x) + '/' + str(b//x))
a, b = list(map(int, input().split(' ')))
denom = 2**a
dp = [0] * (a+1)
for i in range(1, b):
	dp[i] = 2**i
dp[b] = 2**b-1
for i in range(b+1, a+1):
	dp[i] = sum(dp[i-b:i])

print((simp(2**a-dp[-1], 2**a)))


#!/usr/bin/env python2

def gcd(a,b):
	while b:
		a,b=b,a%b
	return a

n, k = list(map(int, input().split()))
q = 2**n
a = [0] * (n+1)
a[0] = 1
for i in range(1,n+1):
	a[i] = a[i-1]*2
	if i == k:
		a[i] -= 1
	elif i > k:
		a[i] -= a[i-k-1]
p = a[n]
p = q - p
d = gcd(p, q)
p = p // d
q = q // d
print(( '{}/{}'.format(p, q) ))