Problem:


Score : 300 points

Problem Statement

Snuke has a fair N-sided die that shows the integers from 1 to N with equal probability and a fair coin. He will play the following game with them:

Throw the die. The current score is the result of the die.

As long as the score is between 1 and K-1 (inclusive), keep flipping the coin. The score is doubled each time the coin lands heads up, and the score becomes 0 if the coin lands tails up.

The game ends when the score becomes 0 or becomes K or above. Snuke wins if the score is K or above, and loses if the score is 0.

You are given N and K. Find the probability that Snuke wins the game.

Constraints

1 ≤ N ≤ 10^5

1 ≤ K ≤ 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the probability that Snuke wins the game. The output is considered correct when the absolute or relative error is at most 10^{-9}.

Sample Input 1

3 10

Sample Output 1

0.145833333333

If the die shows 1, Snuke needs to get four consecutive heads from four coin flips to obtain a score of 10 or above. The probability of this happening is \frac{1}{3} \times (\frac{1}{2})^4 = \frac{1}{48}.

If the die shows 2, Snuke needs to get three consecutive heads from three coin flips to obtain a score of 10 or above. The probability of this happening is \frac{1}{3} \times (\frac{1}{2})^3 = \frac{1}{24}.

If the die shows 3, Snuke needs to get two consecutive heads from two coin flips to obtain a score of 10 or above. The probability of this happening is \frac{1}{3} \times (\frac{1}{2})^2 = \frac{1}{12}.

Thus, the probability that Snuke wins is \frac{1}{48} + \frac{1}{24} + \frac{1}{12} = \frac{7}{48} \simeq 0.1458333333.

Sample Input 2

100000 5

Sample Output 2

0.999973749998



Sample input:
3 10


Sample output:
0.145833333333

Submission status: Accepted

Solution code:
N,K=map(int,input().split())

if N<K:
    total=0
    for i in range(1,N+1):
        for j in range(1000):
            if i*2**j<K<=i*2**(j+1):
                total+=(1/N)*(1/2)**(j+1)
                break
elif N>=K:
    total=0
    for i in range(K,N+1):
        total+=(1/N)*1
    for i in range(1,K):
        for j in range(1000):
            if i*2**j<K<=i*2**(j+1):
                total+=(1/N)*(1/2)**(j+1)
                break   
print(total)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
lis = []
for i in range(1,n+1):
    count = 0
    while i < k:
        i *= 2
        count += 1
    lis.append(count)
result = 0
for i in lis:
    result += 1 / n * 0.5 **i
print(result)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
B = []
for i in range(1,N+1):
    count = 0
    while i < K:
        i *= 2
        count += 1
    B.append(count)

result = 0
for a in B:
    result += 1/N*0.5**a

print(result)

Submission status: Accepted

Solution code:

import math
N, K = map(int, input().split())

ans=0
for i in range(1,N+1,1):
    point = i
    count = 0
    if i>=K:
        ans +=1
    else:
        while point < K:
            point *= 2
            count += 1
        ans += 1/(2**count)

print(ans/N)

Submission status: Accepted

Solution code:
N, K = input().split()
N = int(N)
K = int(K)

probability = []

for i in range(1, N+1):
    count = 0
    while i < K:
       i = i * 2
       count += 1
    probability.append((1/N)*(1/2)**count)   

result = 0
for i in probability:
    result = result + i

print(result)

Submission status: Accepted

Solution code:
import math

N, K = map(int, input().split())

ans = 0
for n in range(1,N+1):
  ans += ((0.5) ** max(math.ceil(math.log2(K/n)), 0))/N
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math


def main():
    n, k = map(int, input().split())
    p = 0
    for i in range(1, n + 1):
        head_num = math.ceil(math.log(k / i, 2.0))
        head_num = max(head_num, 0)
        p += 1 / n * ((0.5) ** head_num)
    print(p)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

N, K = map(int, input().split())

ans = 0

if K == 1:
    print(1)
    exit()

for i in range(1, min(N+1, K)):
    #print(2 ** -np.ceil(np.log2(K/i)))
    ans += 2 ** -math.ceil(math.log2(K/i))

ans = ans/N

if N > K:
    ans += (N-K+1)/N    

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ans=0
for i in range(1, n+1):
    tmp=1/n
    p=i
    while p<k:
        p=2*p
        tmp=tmp/2
    ans+=tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n, k = map(int, readline().split())
    ans = 0.
    for i in range(1, n+1):
        cnt = 0
        s = i
        while s<=k-1:
            s *= 2
            cnt += 1
        ans += 1/n * pow(2, -cnt)
    print('{:.12f}'.format(ans))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

for i in range(1, n+1):
  if i >= k:
    ans += 1/n
  else:  
    ans += 1/n*((1/2)**math.ceil(math.log2(k/i)))
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import math

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n, k = IN()
	#s = input()
	r=0
	for i in range(1, n+1):
		a = math.ceil(math.log2(max(1,(k+i-1)//i)))
		#print(i, a, i*(2**a),k)
		ra = (1/2)**a
		r+=ra
		#print(ra)
		
	return r/n
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
def resolve():
    N, K = [int(i) for i in input().split()]
    import math
    ans = 0
    for i in range(1, N + 1):
        if i < K:
            coin = math.ceil(math.log2(K / i))
            ans += (1 / N) * ((1 / 2)**coin)
        else:
            ans += (1 / N)
    print(ans)


resolve()

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,k = iim()
ans = 0
for i in range(1,min(k,n+1)):
    num = i
    cnt = 0
    while num<k:
        cnt += 1
        num *= 2
#    print(0.5**cnt)
    ans += 0.5**cnt

ans += max(n-k+1,0)
print(ans/n)

Submission status: Accepted

Solution code:
from math import log2, ceil
n, k = map(int, input().split())
ans = 0
for i in range(1, n + 1):
    if i >= k:
        ans += 1
    else:
        ans += pow(0.5, ceil(log2(k / i)))
print(ans / n)

Submission status: Accepted

Solution code:
def c_dice_and_coin():
    from math import ceil, log2
    N, K = [int(i) for i in input().split()]

    ans = 1 / N * sum(1 / 2**max(ceil(log2(K / d)), 0) for d in range(1, N + 1))
    return round(ans, 12)

print(c_dice_and_coin())

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

def double(n, k):
    num = n
    cnt = 0
    while True:
        if num < k:
            cnt += 1
            num *= 2
        else:
            break
    return cnt

N, K = getNM()
ans = max(0, N - K + 1) / N
for i in range(1, min(N + 1, K)):
    prob = double(i, K)
    ans += 1 / ((2 ** prob) * N)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ans = 0
DP = [0] * K
ans = 0
for i in range(1, N + 1):
    c = 0
    tmp = i
    while K > tmp:
        tmp = tmp * 2
        c += 1
    ans += (1 / N) * 0.5 ** c

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())

ex=0
probabilitys=[]
for i in range(n):
    number = n - i
    while True:
        if number*2**ex>=k:
            break
        ex+=1
    probabilitys.append((1/n)*((1/2)**ex))
print(sum(probabilitys))

Submission status: Accepted

Solution code:
from fractions import Fraction

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

def toss(j, k):
    cnt = 0
    while j <= k-1:
        j *= 2
        cnt +=1
    return cnt

ans = 0
for i in range(1, n+1):#サイコロの目ごとに場合分け
    ans += Fraction(1, 2**toss(i,k))
    
ans = Fraction(ans, n)
print(float(ans))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())

ans = 0

for i in range(1, N+1):
  l = 0
  j = i
  
  while j < K:
    j = j * 2
    l += 1
  
  ans += 1.0/N * (0.5 ** l)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

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

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n = n//a
    count += 1
  if a**count == n:
    return count
  else:
    return count+1

#############
# Main Code #
#############

N,K = IL()

def count(a):
  c = 0
  while a<K:
    c += 1
    a *= 2

  return c

l = [ count(i) for i in range(1,N+1)]

P(sum(pow(0.5,i) for i in l)/N)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
import math
ans =0
for n in range(1,N+1):
  if math.ceil(math.log2(K/n))>=1:
    ans += (1/N) * (1/2)**(math.ceil(math.log2(K/n)))
  else:
    ans += 1/N
print(ans)

Submission status: Accepted

Solution code:
#!python3

def LI():
    return list(map(int, input().split()))

# input
N, K = LI()


def p(x):
    ret = 1
    while x < K:
        ret /= 2
        x *= 2
    return ret


def main():
    ans = 0
    for i in range(1, N + 1):
        ans += p(i)

    ans /= N
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
dl = []
for i in range(n):
  d = i + 1
  dl.append(d)
bnl = []
rnl = []
for i in range(n):
  rn = dl[i]
  bn = 0
  while (True):
    if rn < k:
      rn *= 2
      bn += 1
    else:
      break
  if bn >= 0:
    bnl.append(bn)
    rnl.append(rn)
pl = []
for i in range(n):
  p = (1 / n) * (1 / 2) ** bnl[i]
  pl.append(p)
print(sum(pl))

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
a = 0
for i in range(1,N+1):
  nankai = 0
  while 2**(nankai)*i  < K  :
    nankai += 1
  a += 1/(N*(2**nankai))
print(a)

Submission status: Accepted

Solution code:
from fractions import Fraction

N, K = map(int, input().split())

y = Fraction(1, N)


count = 0
for i in range(1, N + 1):
    kakuritu = 1
    while 1 <= i and i <= K - 1:
        i *= 2
        kakuritu /= 2
        if (i <= K):
            continue
        elif (i >= K):
            break
    count += kakuritu
print("{:.12f}".format(count * float(y)))

Submission status: Accepted

Solution code:
def get_c(p, k):
    c = 0
    while 1:
        if p * pow(2, c) >= k:
            return c
        c += 1


# input
N, K = map(int, input().split())

# check
prob = [1 / N] * N
for p, i in zip(range(1, N + 1), range(N)):
    c = get_c(p, K)
    prob[i] *= (1 / 2) ** c

print(sum(prob))

Submission status: Accepted

Solution code:
def f(a,k):
    p=0
    while a<k:
        a*=2
        p+=1
    return p

n,k=map(int,input().split())
a=float()
for i in range(1,n+1):
    a+=1/(2**f(i,k))
print('{:.18f}'.format(a/n))

Submission status: Accepted

Solution code:
import math

log = math.log2
ceil = math.ceil

def main():
    N, K = map(int, input().split())
    ans = 0
    for i in range(1, N+1):
        s = ceil(log(K)-log(i))
        ans += 1/N * min(1, pow(1/2, s))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())

result = 0

for i in range(1,N+1):
    a = 1
    c = 0
    while a < K/i:
        a = a*2
        c += 1
    result += (1/N) * (1/2)**c

print(result)

Submission status: Accepted

Solution code:
n,k = [int(x) for x in input().split()]

ans = 0

for i in range(1, n+1):
    tmp = 1/n
    now = i
    while now < k:
        now *= 2
        tmp /= 2
    ans += tmp
print(ans)

Submission status: Accepted

Solution code:
from decimal import Decimal
N,K = map(int,input().split())
ans = 0
for i in range(1,N+1):
    num = 1
    while i*num < K:
        num *= 2
    ans += Decimal(1/num/N)
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
a = 0
for i in range(1,N+1):
  nankai = 0
  while 2**(nankai)*i  < K  :
    nankai += 1
  a += 1/(N*(2**nankai))
print(a)

Submission status: Accepted

Solution code:
import math
n, k = map(int, input().split())

ans = 0
ma = 10**9
for i in range(1, n+1):
    p = math.ceil(math.log2(k) - math.log2(i))
    if p >= 1:
        ans += 1/(n*2**p)
    else:
        ans += 1/n

print(ans)

Submission status: Accepted

Solution code:
from math import log2,ceil
n,k = map(int,input().split())
ans = 0
for i in range(1,n+1):
    if i < k:
        ans += 1/2**(ceil(log2(k/i)))
    else:
        ans += 1
ans /= n
print('{}'.format(ans))

Submission status: Accepted

Solution code:
from math import log2,ceil
n,k = map(int,input().split())
ans = 0
for i in range(1,n+1):
    if i < k:
        ans += 1/2**(ceil(log2(k/i)))
    else:
        ans += 1
ans /= n
print('{:.15f}'.format(ans))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
L = [''] * n
for i in range(1, n + 1):
    j = 0
    while i * (2 ** j) < k:
        j += 1
    L[i - 1] = j
S = 0
for k in L:
    S += 1 / (2 ** k)
print(S / n)

Submission status: Accepted

Solution code:
import math

N, K = map(int, input().split(' '))

s = 0

for i in range(1, N + 1):
    s += 1 / math.pow(2, max(0, math.ceil(math.log2(K) - math.log2(i))))

print(s / N)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    P = 0
    for i in range(1,N+1):
        value = i
        cnt = 0
        while K > value:
            cnt += 1
            value *= 2
        P += 1/N * (1/2)**cnt
    print(P)
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
ans = 0
for i in range(1,n+1):
    p = 0
    while i < k:
        i = 2*i
        p += 1
    ans += 1/(2**p*n)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, K: int):
    ans = 0.0
    if N >= K:
        ans += (N - K + 1) / N
    k = K
    p = 1.0
    while k > 1:
        j = -(-k // 2)
        p /= 2.0
        ans += (min(k, N + 1) - min(j, N + 1)) / N * p
        k = j
    print(ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=[int(x) for x in input().rstrip().split()]
ans=0
for i in range(1,n+1):
  now=i
  cnt=0
  while(True):
    if k<=now:
      break
    cnt+=1
    now=now*2
  # print(now)
  ans+=(1/n)*(1/2)**cnt
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

from math import log2, ceil


def main():
  n, k = map(int, input().strip().split())
  
  p = 0
  for i in range(1, n+1):
    s = k / i  # 10 / 3
    t = max(ceil(log2(s)), 0)
    p += 1/n * (0.5 ** t)
 
  print(p)



if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())

import math
import numpy as np
def lambda_p(k,n):
  m=math.ceil(math.log(k,2))
  p=0
  for ii in np.arange(1,n+1):
    p+=1/n*(1/2)**math.ceil(math.log(k/ii,2))
  return p

def lambda_nk(n,k):
  return k/n

if n>k:
  r=lambda_nk(n,k)*lambda_p(k,k)+(1-lambda_nk(n,k))
else:
  r=lambda_p(k,n)
print(r)

Submission status: Accepted

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
import math
import itertools
import heapq
import sys
sys.setrecursionlimit(10**6)

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
input_list = lambda : list(map(int,input().split()))


n,k=input_list()

ans=0

for i in range(1,n+1):
    cal=math.ceil(math.log(k/i,2))
    cal=max(0,cal)
    ans+=(1/2)**(cal)

print(ans/n)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    ans = 0
    for i in range(1, N+1):
        score = i
        count = 0
        while score < K:
            score *= 2
            count += 1
        ans += (1/N) * ((1/2)**count)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
N,K = map(int,input().split())
print((1/N)*sum([1/pow(2,math.ceil(math.log2(max(K/i,1)))) for i in range(1,N+1)]))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
p = 0
for i in range(1,n+1):
  times = 0
  while i < k:
    i *= 2
    times += 1
  p += 1/(2**times)

print(p/n)

Submission status: Accepted

Solution code:
# 初期入力
import math
from math import ceil
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())

num_prob =1/N
ans =0
for i in range(1,N+1):
    
    if K <=i:
        ans =(ans + num_prob)
    else:
        x =ceil(math.log2(K/i))
        ans += num_prob *(0.5**x) #サイコロの確立と表が出続ける確率
print(ans)

Submission status: Accepted

Solution code:
def win(N, n, K):
  cnt = n
  inc = 0
  while cnt<K:
    cnt *= 2
    inc += 1
  return (1/N)*0.5**inc
  

N, K = [int(i) for i in input().strip().split()]

total = 0
for n in range(1, N+1): 
  total += win(N, n, K)
print(total)

Submission status: Accepted

Solution code:
import math
N, K = list(map(int, input().split()))
p = 0
for n in range(1, N + 1):
    if n >= K:
        p += 1
    else:
        p += (0.5 ** math.ceil(math.log2(K / n)))
print(p / N)

Submission status: Accepted

Solution code:
import math 
n, k = map(int, input().split())

rate = 0
for i in range(1, n + 1):
    cnt = 0
    if i < k:
        cnt = math.ceil(math.log2(k / i))
    rate += 1 / n * 0.5 ** cnt

print(rate)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = 0

for i in range(1, N+1):
    if i >= K:
        P += (N-i+1) / N
        break

    else:
        n = 1
        while i*n < K:
            n *= 2
        P += 1 / (N*n)


print(P)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
ans = 0
for i in range(1, N+1):
	if i >= K:
		ans += 1/N
	else:
		ans += (1/N) * ((1/2)**ceil(log2(K/i)))
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()

P = 1/N
ans = max(0, (N-K+1)/N)

for i in range(1, min(N+1, K)):
	ans += P*0.5**(ceil(log2(K/i)))

print(ans)

Submission status: Accepted

Solution code:
import math as m


N, K = map(int, input().split())
P = 0

for i in range(1, N+1):
    if i >= K:
        P += (N-i+1) / N
        break
    else:
        if m.log2(K/i).is_integer():
            P += 1 / (N*2**(m.log10(K/i)/m.log10(2)))
        else:
            P += 1 / (N*2**int(m.log10(K/i)/m.log10(2) + 1))

print(P)

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools
import copy
n, k = map(int, input().split())

sum = 0
for i in range(1,n+1):
    score = i
    count = 0
    while score < k:
        score *= 2
        count += 1
    sum += (1/n) * (1/2) ** count

print(sum)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())

tmp = 0
ans = 0
for i in range(1, N+1):
    cnt = 0
    while True:
        if i < K:
            i *= 2
            cnt += 1
        else:
            break
    ans += N**(-1) * .5**cnt
print(ans)

Submission status: Accepted

Solution code:
[n, k] = [int(i) for i in input().split()]
total = 0
for i in range(1, n+1):
    point = i
    prob = 1/n
    while(point < k):
        point *= 2
        prob /= 2
    total += prob
print(total)

Submission status: Accepted

Solution code:
import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))
n,k = map(int, stdin.readline().rstrip().split())
#numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
#word = [stdin.readline().rstrip() for _ in range(n)]
#number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
#zeros = [[0] * w for i in range(h)]

win = 0

if n>k:
    win += (n-k) / n
    limit = k
else:
    limit = n

base = 1 / n
for i in range(1,limit+1):
    u = i
    j = 0
    while u < k:
        u *= 2
        j += 1
    win += base * (1/2)**j

print(win)

Submission status: Accepted

Solution code:
import math
N, K = map(int, input().split())

p_win = 0
if N >= K:
    p_win += (N - K + 1) / N

k = K
i = 1
while k >= 1:
    half_k = k / 2
    if N < k:
        num_nums = max(N - math.ceil(half_k) + 1, 0)
    else:
        num_nums = math.ceil(k) - math.ceil(half_k)
    p_i = (num_nums/N) * ((1/2)**i)
    # print(f'{i}: {half_k=} <= n < {k=}, {num_nums=}, {p_i=}')
    p_win += p_i
    i += 1
    k = half_k

print(p_win)

Submission status: Accepted

Solution code:
import math

n,k = map(int,input().split(" "))
ret = 0
for i in range(1,n+1):
    if i > k:
        fraq = 0.0
    else:
        fraq = math.ceil(math.log2(k/i))
    ret += (1/n) * (1/2)**fraq

print(ret)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
 
score = N
counter_tmp = 0
ans = 0
 
 
for i in range(N):
    counter_tmp = 0
    score = i + 1
    while score < K:
        score = score * 2
        counter_tmp += 1
    ans += 1 / (N * (2 ** counter_tmp))
 
print(ans)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))

l = []
for i in range(n):
    score = i+1
    count = 0
    while(1):
        if score >= k:
            break
        score = score*2
        count += 1
    l.append((1/n)*pow((1/2),count))

print(sum(l))

Submission status: Accepted

Solution code:
#N,Kを取得する。
n,k = map(int,input().split())

#確率を保存する配列を用意
v = 0.0

for i in range(1,n+1):  #出目が1～Nまであるので、そのすべてについて調べる。
    #ちょっとiの値を保存する
    t = i
    #何回表を出し続ければいいか？をカウントする変数を用意
    x = 0
    while(t < k):   #得点がK以上になるまで
        t *= 2  #表を出したことにして得点を2倍にする
        x += 1
    
    #一回目にiを出す確率は1/N
    #それからx回表を出し続ける確率は(1/2)^x=0.5^x
    #あとはその積を加算していく。 
    v += 1.0 / n * 0.5**x
print(v)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())

probs = 0
for i in range(1, N + 1):
    point = i
    cnt = 0
    while point < K:
        point *= 2
        cnt += 1
    probs += (1 / N) * (0.5 ** cnt)

print(probs)

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
N, K = inpl()
X = [0] + [1/N if i <= N else 0 for i in range(1, K)]
w = max(0, N-K+1)/N

for i in range(K):
    if (i*2 >= K):
        w += X[i]/2
    else:
        X[i*2] += X[i]/2
print(w)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
ans = 0
for i in range(1,n+1):
    tmp = i+0
    x = 1/n
    while i<k:
        i*=2
        x/=2
    ans+=x
print(ans)

Submission status: Accepted

Solution code:
import math
n,k = map(int,input().split())

v = 0.0
for i in range(1,n+1):
    t = i
    x = 0
    while(t < k):
        t *= 2
        x += 1
    v += 1.0 / n * 0.5**x
print(v)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    possible = 0
    for i in range(1, N + 1):
        this_poss = 1
        if i < K:
            t = i
            while t < K:
                this_poss *= 0.5
                t *= 2
        possible += this_poss / N
    print(possible)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
cast = 0
mulp = 1
while mulp < k:
  mulp *= 2
  cast += 1
  
ans = 0.0
for i in range(1,1+n):
  if mulp * i >= 2 * k and cast > 0:
    cast -= 1
    mulp //= 2
  ans += 2 ** (-cast)
print(ans/n)

Submission status: Accepted

Solution code:
import math
N,K = map(int,input().split())


print('{:.12f}'.format(sum([(1/N)*(0.5)**math.ceil(math.log2(math.ceil(K/i))) if i<K else 1/N for i in range(1,N+1)])))

Submission status: Accepted

Solution code:
import math

n,k = map(int,input().split())
c = 0
for i in range(1,n+1):
  if i >= k:
    c += 1
  else:
    s = math.ceil(math.log2(k/i))
    c += (1/2)**s
print(c/n)

Submission status: Accepted

Solution code:
#print#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,K=pin()
    MAGICNUMBER=17 #2**MAGICNUMBER>10**5>=M
    ans_x3=0
    for i in range(1,N+1):
        temp=i
        coins=0
        for j in range(MAGICNUMBER+1):
            if temp>=K:
                coins=j
                break
            temp*=2
        #print()
        ans_x3+=(2**(0-coins))*(2**30)
    t=int(ans_x3//N)
    print(t/(2**30))   
#%%submit!
resolve()

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
P = np.arange(N, dtype=np.int64) + 1
count = 0
total = 0
prev = 0
ans = 0
while True:
    now = (P >= K).sum()
    total += now - prev
    ans += (now - prev) / (1 << count)
    if total == N:
        break
    P <<= 1
    count += 1
    prev = now
print(ans / N)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed May 13 12:04:27 2020

@author: shinba
"""

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

ans = 0

for i in range(1,n+1):
    cnt = 0
    while i < k:
        i *= 2
        cnt += 1
    ans += (0.5)**cnt/n

print(ans)