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:
def sub():
    N, K = [int(e) for e in input().split(" ")]

    pOne = (N-K+1) / N
    if pOne < 0:
        pOne = 0.0

    M = min(K-1, N)
    k = 2
    count = 1
    tmpM = M + 0
    buf = []
    for i in range(M):
        tmpM = M-i
        while True:
            v = tmpM*k
            if v >= K:
                buf.append(count)
                break
            k = 2*k
            count = count + 1
    twos = [0.5]
    for _ in range(count-1):
        t = twos[-1] * 0.5
        twos.append(t)
    
    pp = [twos[b-1] / N for b in buf]
    pTwo = sum(pp)
    print(pOne + pTwo)
    


sub()

Submission status: Accepted

Solution code:
import math

N, K = map(int, input().split())
minNK = min(N, K-1)

sumA = 0

for i in range(1, minNK+1):
    c, k = 0, i
    while k < K:
        c, k = c+1, k*2
    #print(i, c, k)
    sumA += ( math.pow(0.5, c) / float(N))
#print(sumA)

if N >= K:
    sumA += (float(N - K + 1) / float(N))
print(sumA)

Submission status: Accepted

Solution code:
import math
N, K = (int(x) for x in input().split())
prob = 0
for i in range(1,N+1):
    a = i
    b = 1
    while a < K:
        a *= 2
        b *= 0.50000000000
    prob += b
print(prob / N)

Submission status: Accepted

Solution code:
import math
n,k=map(int,input().split())
ans=0
for i in range(1,n+1):
    ans+=(1/2)**math.ceil(max(math.log2(k/i),0))
print(ans/n)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, K = LI()
    ans = 0
    for i in range(1, N + 1):
        if i >= K:
            ans += 1
        else:
            times = -(-K // i)
            bits = (times - 1).bit_length()
            ans += 0.5 ** bits
    ans /= N
    return ans

print(main())

Submission status: Accepted

Solution code:
import numpy as np
import math

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

if N > K: 
    prob_base = (N-K) / N
    prob = 0
    
    for i in range(1, K+1):
        x = math.ceil(np.log2(K/i))
        prob += (1/N) * (1/2)**x
        
    print(prob_base + prob)
    
else:
    prob = 0
    for i in range(1, N+1):
        x = math.ceil(np.log2(K/i))
        prob += (1/N) * (1/2)**x
        
    print(prob)

Submission status: Accepted

Solution code:
from math import log,ceil
def solve():
    N,K = map(int, input().split())
    # if N == 1 and K != 1:
    #     print("0")
    #     exit()
        
    # elif N == 1 and K ==  1:
    #     print("1")
    #     exit(0)

    
    ans = 0
    for x in range(1, N+1): # xは初期値
        kaisuu = ceil( log( K / x, 2))
        # tmp = pow(0.5, kaisuu)
        tmp = 1/N
        for i in range(kaisuu):
            tmp *= 0.5
        ans += tmp 
    # ans /= N
    print(ans)
        

    
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
l = list(map(int, input().split()))
num = l[0]
k = l[1]
baro=[]
ans=[]
for j in range(1,num+1):
    for i in range (100000):
        if j * 2 **i >= k:
            baro.append(i) 
            break
for m in baro:
    ans.append((1/num)*(1/2)**m)

print(sum(ans))

Submission status: Accepted

Solution code:
Input = input().split()
N = int(Input[0])
K = int(Input[1])

ret = float(0)

for i in range(1,N+1):
    tmp = float(1/N)
    now = i
    while(now<K):
        now *= 2
        tmp /= 2
    ret += tmp

print(ret)

Submission status: Accepted

Solution code:
from decimal import *

import math

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

# 計算しない範囲を求める
# 100 10 なら 100-10 + 1/100はかつ
result = 0

for i in range(1,N + 1):
    tmp = 1/N
    i_tmp = i
    while i_tmp < K:
        tmp /= 2
        i_tmp *= 2
        #print(i_tmp)
    result += tmp
print(result)





#print(''.join(S))

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
prob = 0
for n in range(1, N+1):
  #print(n)
  #print("hogehoge")
  if(K <= n):
   prob = prob + 1
   continue
  else:
   #print(bin(n))
   #print(bin(K))
   len_bin_n = len(str(bin(n)))
   len_bin_k = len(str(bin(K)))
   min_rest_number_of_front = len_bin_k - len_bin_n
   if(K <= n * pow(2, min_rest_number_of_front)):
    prob = prob + 1/pow(2,min_rest_number_of_front)
    #print(1/pow(2,min_rest_number_of_front))
   else:
    prob = prob + 1/pow(2,min_rest_number_of_front+1)
    #print(1/pow(2,min_rest_number_of_front+1))
 
result = (1/N) * prob
print(result)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
r = 0
for i in range(1, n + 1):
    if i >= k:
        print((r + (n - k + 1))/ n)
        break
    a = i
    c = 0
    while a < k:
        a *= 2
        c += 1
    r += (1 / 2) ** c
else:
    print(r / n)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ans = 0
for i in range(1, n+1):
    for j in range(18):
        if i >= k:
            break
        i *= 2
    ans += (1 / n) * (0.5) ** j
print('{:.12f}'.format(ans))

Submission status: Accepted

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

import math

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

sum = 0
list = []
for n in range(1,N+1):
    if n < K:
        x = abs(math.log2(K/n))
        x_ceil = math.ceil(x)
        sum += pow(0.5, x_ceil)/N
    else:
        sum += 1/N

print(sum)

Submission status: Accepted

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

b=1
S=0
a=0
m=0
for i in range(1,n+1):
    b=i
    for j in range(0,100000):
        if b>=k:
            m=j
            break
        else:
            b=b*2
            continue
    

    S=S+(1/(n*2**(m)))

print(S)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ans=0
for i in range(1,n+1):
    count=0
    while True:
        if i>=k:
            break
        i=i*2
        count+=1
    ans+=1/n*((1/2)**count)

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
a=input().split()
a=list(map(int,a))
ini=a[0]
obj=a[1]
poss=0
i=1
divini=1
pot=0
posini=i/ini
while i<=ini:
  pot=0
  divini=i
  if divini>=obj:
    poss=poss+(1/ini)
  else:  
    while divini<obj:
      divini=divini*2
      pot+=1
    pg=(1/2)**pot
    poss=poss+(pg*posini)
  i+=1  
print(poss)

Submission status: Accepted

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

total = 0
for n in range(1,N+1):
	tmp = 1/ N
	now = n
	while now < K:
		now *= 2
		tmp /= 2
	
	total += tmp
	
print(total)

Submission status: Accepted

Solution code:
import numpy as np
 
N, K = map(int, input().split())
 
def get_x(n, K):
    if n >= K:
        return 0
    else:
        x_raw = np.log2(K) - np.log2(n)
        return np.ceil(x_raw)

def get_prob(n, K):
    x = get_x(n, K)
    if x == 0:
        return 1
    else:
        return (1/2)**x
    
ans = np.mean([get_prob(n, K) for n in range(1, N+1)], dtype=np.float64)
 
print('{0:.12f}'.format(ans))

Submission status: Accepted

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

import math

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

sum = 0
list = []
for n in range(1,N+1):
    if n < K:
        x = abs(math.log2(K/n))
        x_ceil = math.ceil(x)
        sum += pow(0.5, x_ceil)/N
    else:
        x_ceil = 1
        sum += 1/N

print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math


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

Submission status: Accepted

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

X = [0] * N

for i in range(1,N+1):
    j = i
    tmp = 1

    while(j<K):
        j *= 2
        tmp /= 2

    X[i-1] = tmp

print(sum(X) / N)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
N, K = map(int, input().split())
r = 0
for i in range(1, N+1):
    tmp = 1/N
    now = i
    while(now < K):
        now *= 2
        tmp /= 2
    r += tmp
print(r)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(1,n+1):
    i_1 = 0
    while True:
        if i >= k:
            l.append(i_1)
            break
        i*= 2
        i_1 += 1

lis = [(1/n) * (1/2)**i for i in l]

print(sum(lis))

Submission status: Accepted

Solution code:
n,k=input().split(' ')
n,k=int(n),int(k)
score=int()
r=1/n
for dice in range(1,n+1):
        counter=0
        mul=dice
        while mul<k:
            mul=mul*2
            counter+=1
        score+=r*((.5)**counter)

print(round(score,12))

Submission status: Accepted

Solution code:
import math
n, k = map(int, input().split())
p = 0
if n >= k:
  p += (n-k+1)
for i in range(int(math.log2(k)), -1, -1):
  if n >= math.ceil(k/2**(i)):
    p += (math.ceil(k/2**(i))-math.ceil(k/2**(i+1)))/2**(i+1)
  else:
    p += (n-math.ceil(k/2**(i+1))+1)/2**(i+1)
    break
print(p/n)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ans = 0.0
for i in range(1, n + 1):
  hops = 0
  while i < k:
    hops += 1
    i *= 2
  ans += pow(1.0 / 2.0, hops)
ans /= n
print('{:.10f}'.format(ans))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
lopFlg = True
ansLst = 0
ans = 0
for i in range(1, N + 1):
    tmp = i * 2
    cnt = 1
    while True:
        if i >= K:
            ans += 1
            break
        if K > tmp:
            tmp = tmp * 2
            cnt += 1
        else:
            ans += float(1 / (2 ** cnt))
            break

ans = 1 / N * ans
print(ans)

Submission status: Accepted

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

ans = 0
ans1 = 0
j = 1
flag = False
for i in range(n, 0, -1):

    if(i >= k):
        ans1 += 1
        continue

    if(flag == False):
        flag = True
        while(i*2**j < k): j += 1

        tmp = j
        ans += 1
    else:
        while(i*2**j >= k): j -= 1
        j += 1

        if(tmp != j):
            ans *= 2
            ans += 1
            tmp = j
        else: ans += 1

print((ans+ans1*2**j) / (n*2**j))

Submission status: Accepted

Solution code:
import decimal
 
 
def main():
    N, K = map(int, input().split())
    ans = 0
    for n in range(1, N + 1):
        s = 0
        s += n
        c = 0
        while K > s:
            s *= 2
            c += 1
        ans += decimal.Decimal((1 / N) * (1 / 2) ** c)
    print(ans)
 
 
main()

Submission status: Accepted

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

for i in range(N):
    n = i + 1
    if n < K:
        Sum += pow(0.5, math.ceil(math.log(K/n, 2)))
    else:
        Sum += 1
Sum = Sum / N
print(Sum)

Submission status: Accepted

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

i = 1
temp = 1
a = 0


# count decide
def countt(temp):
    count = 0
    while temp < k:
        temp *= 2
        count += 1
    return count


while i <= n:
    if i < k:
        count = int(countt(i))
        s = (1 / n * ((1 / 2) ** count))
        i += 1
        a += s
        count -= 1
    else:
        a += 1 / n
        i += 1
print(a)

Submission status: Accepted

Solution code:
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#n=int(input())
#li=input().split()
#import fractions
#n=int(input())
#S=input()
import math

lis=list(map(int,input().split()))
ans=0
for i in range(1,lis[0]+1):
    s=0
    while True:
        if i*(2**s)>=lis[1]:
            ans+=1/(lis[0]*(2**s))
            break
        else:
            s+=1







print(ans)

Submission status: Accepted

Solution code:
import math

n, m = input().split()
N = int(n)
K = int(m)

NN = (N / 2) * (N + 1)

NN = NN / N

result = 0.0
for i in range(N):
    X = K / (i + 1)
    X = math.log(X, 2)
    if X == int(X):
        pass
    else:
        X = math.floor(X) + 1
    if X < 0:
        result += (1 / N)
    else:
        result += (1 / N) * ((1/2) ** X)
print(result)

Submission status: Accepted

Solution code:
import math
dice,point=map(int,input().split())
percent = 0.0
power = 0
for i in range(1,dice+1):
    for j in range(20):
        if (point <= i *(2 **j)):
            power = j
            break


    current = (1 / dice) * (1/2) ** power
    percent = percent + current


print(percent)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
i=0
p=0
u=0
sum_a=0
number=[]
if N>=K:
    num = K-1
else:
    num = N
for a in range(1,num+1):
    sum_a=a
    while u<=1:
        sum_a1=sum_a*2
        sum_a =+sum_a1
        #print(sum_a)
        i=i+1
        #print(sum_a)
        if (sum_a)>=K:
            u=2
    number.append(i)
    u=0
    i=0
    sum_a1=0
if num!=N:
    for i in range(N):
        number.append(0)
for i in range(N):
    if number[i]!=0:
        a=(1/2)**int(number[i])
        p = p +((1/N)*a)
        #print(p)
    else:
        p=p + (1/N)
    

print(p)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

log = math.log(8, 2)

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

sum = 0

for i in range(1, n+1):
    exp  = math.log(k/i, 0.5)
    current = 1/n * 0.5**(math.ceil(abs(exp)))
    if exp >= 0:
        exp = 0
        current = 1/n 
    sum += current

if k == 1:
    print(1)
else:
    print(sum)

Submission status: Accepted

Solution code:
from math import ceil

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

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

for i in range(20):
  if( K/(2**(i+1)) <= N < K/(2**i) ):
    ans += ( N +1 - ceil( K/(2**(i+1)) ) )/N / (2**(i+1))
  if( N > K/(2**i)):
    ans += ( ceil( K/(2**i) ) - ceil( K/(2**(i+1)) ) )/N / (2**(i+1))

print(ans)

Submission status: Accepted

Solution code:
import math
n,k=map(int,input().split())
p=1/2
p0=1/n
pp=0
M=math.ceil(math.log2(k))
m=math.ceil(math.log2(k/n))
for i in range(1,min(k+1,n+1)):
    pp+=p0*(p**math.ceil(math.log2(k/i)))
if n>k:
    pp+=p0*(n-k)
print(pp)

Submission status: Accepted

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

mod = n
qtdMin = 1/n
mid = 1
while(mod<k):
    mod<<=1
    qtdMin*=0.5
    mid<<=1
    
res = 0

for i in range(k,n):
    res += (1/n)

mod = qtdMin
res+=mod

for i in range(min(n,k)-1,0,-1):
    if(i*mid < k):
        mod*=0.5
        mid<<=1
    res+= mod
print(res)

Submission status: Accepted

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

prob = [0] * N

for i in range(1,N+1):
    tmp = i
    for j in range(1,K+1):
        if tmp >= K:
            prob[i-1] = 1
            break
        tmp *= 2
        if tmp >= K:
            prob[i-1] = ((1/2)**j)
            break

ans = 0
tmp = 0

for i in range(N):
    tmp += prob[i]
    ans = 1/N * tmp

print(ans)

Submission status: Accepted

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

P = [2**x for x in range(18)]

p_max = 0
for p in P:
    if K <= p:
        p_max = p
        break

ans = 0
for i in range(1,N+1):
    for j in range(18):
        if max(K/i, 1) > p_max/2**j:
            #print('{}, {}'.format(K/i, j-1))
            ans += 2**(j-1)
            break
print(ans/N/p_max)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from decimal import Decimal
li = input().split()
n = int(li[0])
k = int(li[1])

# n面サイコロ kは得点

# 1/nの確率で1~nが出る
# 勝つためにx回表を出し続ければ良い
# 目 * 2^x >= kとなればよい

answer = 0
for i in range(n):
    dicenum = i + 1
    winline = dicenum
    x = 0
    while winline < k:
        x += 1
        winline = dicenum * (2**x)
    if dicenum == 1:
        first_x = x
        bunbo = n * 2**x #initialize
        bunsi = 1 #initialize
    elif x == 0:
        bunsi += 2**first_x
    else:
        bunsi += 2**(first_x - x)

answer = Decimal(str(bunsi)) / Decimal(str(bunbo))
print("{:.12f}".format(answer))

Submission status: Accepted

Solution code:
import sys
import math
 
a,b=map(int, input().split())
 
probablity = 0.0
 
for i in range(a):
  ceil = math.ceil(math.log2(b / (i + 1)))
  if(ceil < 0):
    ceil = 0
    
  probablity = probablity + 1 / (a * 2 ** ceil)
  
print(probablity)

Submission status: Accepted

Solution code:
import math

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

k = []
n = N
tmp = K
i = 0
while tmp >= 2:
    k.append(tmp)
    tmp = tmp / 2
k.append(tmp)
k.append(1)
        
ans = 0
for i in range(len(k)):
    if n >= k[i]:
        ans += math.floor(n + 1 - k[i]) / (2 ** i)
        n -= math.floor(n + 1 - k[i])

ans = ans / N
print("{}".format(ans))

Submission status: Accepted

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

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

Submission status: Accepted

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

coin_prob = .5

log2 = math.log(2)
logk = math.log(K)
left = logk / log2
def calc(i):
  return max(math.ceil(left - (math.log(i) / log2)), 0)

ans = 0
for i in range(1, N+1):
  n = calc(i)
  ans += coin_prob ** n

print(ans / N)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import Fraction
from decimal import *
N,K = map(int,input().split())
list = []
for i in range(1,N+1):
    if i >= K:
        list.append(float(Fraction(N-i+1,N)))
        break
    n = i
    count = 0
    while n < K:
        n *= 2
        count += 1
    list.append(float(Fraction(1,N)*(Fraction(1,2)**count)))

print(Decimal(sum(list)))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
flag=False
key=0

if n<k: l=n
else: l=k-1

for i in range(l):
    cnt=1
    tmp=(i+1)*2
    while flag==False:
        if k<=tmp:
            break
        tmp*=2
        cnt+=1
    key+=1/n*1/2**cnt


if k<=n:
    key+=1/n*(n-k+1)

print(key)

Submission status: Accepted

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

sum = 0
R = 0

for i in range(1, N+1):
    Sold = sum
    Road = R
    j = 1
    if i >= K:
        sum += 1
    else:
        while i*(2**j) < K:
            j += 1
        X = 1/(2**j)
        collectX = Road + X
        sumNext = Sold + collectX
        DeltaS = sumNext - Sold
        Rnext = collectX - DeltaS
        sum = sumNext
        R = Rnext
#    print(sum, end="|")

print(sum/N)

Submission status: Accepted

Solution code:
import math 

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    s = input().split(' ')
    n = int(s[0])
    k = int(s[1])
    a = 0
    for l in range(1, min(n + 1, k)):
        count = 0
        ll = l
        while True:
            ll = ll * 2
            count = count + 1
            if ll >= k:
                a = a + (1 / (2**count))
                break
    if n < k:
        print(a * (1 / n))
    else:
        print((a * (1 / n)) + ((n - k + 1)/n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

def is_even(x):
    if (x//2)*2 == x:
        return 1
    else:
        return 0

if __name__ == "__main__":
    N,K = map(int,input().split())
    Ks = [K]
    while K > 1:
        K = K/2
        Ks.append(math.ceil(K))
    L = len(Ks)
    for i in range(L):
        if Ks[i] <= N:
            b = i
            break
    prop = 0.0
    if b == 0:
        Ks.insert(0,N+1)
        for i in range(L):
            a = Ks[i] - Ks[i+1]
            c = a
            for i in range(i):
                c = c/2.0
            prop += c
    else:
        Ks.insert(b,N+1)
        for i in range(b,L):
            a = Ks[i] - Ks[i+1]
            c = a
            for i in range(i):
                c = c/2.0
            prop += c
    print(prop/N)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
lopFlg = True
ansLst = 0
ans = 0
for i in range(1, N + 1):
    tmp = i * 2
    cnt = 1
    while True:
        if i >= K:
            ans += 1
            break
        if K > tmp:
            tmp = tmp * 2
            cnt += 1
        else:
            ans += float(1 / (2 ** cnt))
            break

ans = 1 / N * ans
print(ans)

Submission status: Accepted

Solution code:
from math import ceil,pow,log2

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

ans = 0

for i in range(1,n+1):
    coin = 0;
    if i < k:
        coin = ceil(log2(k/i))
    else:
        ans += 1.0 / n
        continue
    ans += 1.0 / n / pow(2.0,coin)

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
potential=[x for x in range(N+1) if x>0 and x<K]
win_count=[]
for x in potential:
    y=1
    able=0
    while 1:
        if x*2**y>=K:
            able=(2**y-1)/(2**y)
            win_count+=[able]
            break
        y+=1

answer=1-(sum(win_count)/N)
#print(potential)
#print(win_count)
print(round(answer,12))

Submission status: Accepted

Solution code:
import math
def sol(inp=input):
    n,k=map(int,inp().split())
    res=0
    for dice_m1 in range(n):
        dice=dice_m1+1
        head=max(0,math.ceil(math.log(k/dice,2)))
        res+=2**-head
    res/=n
    return res
print(sol())

Submission status: Accepted

Solution code:
#ABC126C-DiceAndCoin.py

from sys import stdin
import random

N,K = list(map(int, stdin.readline().split()))

result = 0
i,j = 0, N
X = []

while True:
    if j >= K/(2**i):
        k = int(j-(K/(2**i)-1))
        X.append(k)
        j -= k
    else:
        X.append(0)
    if K/(2**i) < 1:
        break
    i += 1

for i in range(len(X)):
    result += 0.5 ** i * X[i]
result = result * 1/N

print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
#import pdb

line = input()
elem_list = line.split()
n = int(elem_list[0])
k = int(elem_list[1])

ans = 0
tmp_num = k
if n >= k:
    ans += n - k + 1

pw = 1
while(True):
    pw /= 2
    tmp = math.ceil(tmp_num / 2)
    
    if tmp <= 1:
        ans += (tmp_num - 1) * pw
#        print((tmp_num - 1) * pw)
        break
    
    if n < tmp:
        pass
    elif tmp <= n and n < tmp_num:
        ans += ((n - tmp) + 1) * pw
        #print(((n - tmp) + 1) * pw)
    else:
        ans += (tmp_num - tmp) * pw
#        print((tmp_num - tmp) * pw)
    tmp_num = tmp

ans /= n

print(ans)

Submission status: Accepted

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

results = []
for i in range(1, n+1):
    if i >= k/2:
        results.extend([0.5 for _ in range(i, k)])
        results.extend([1 for _ in range(k, n+1)])
        break
    for j in range(1,k):
        if i * 2**j >= k:
            break
    results.append((0.5)**j)
print(sum(results)/n)

Submission status: Accepted

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

l_2 = []
x = 1
while 1:
    l_2.append(2 ** x)
    if 2 ** x > K:
        break
    x += 1

ans = 0
for i in range(N):
    if i + 1 >= K:
        ans += 1 / N
        continue
    for idx, val in enumerate(l_2):
        if (i + 1) * val >= K:
            ans += 1 / N * 0.5 ** (idx + 1)
            break

print("%.20f" % ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,K = map(int,input().split())
def kaisu(num):
  k = []
  cnt = 0
  while True:
    if num > 1:
      cnt+=1
      k.append(cnt)
      num = num/2
    else:
      return k

cnt = 1
z = []
for i in range(N,0,-1):
  if i >= K:
    z.append(1)
  else:
    while True:
      if K/(2**cnt) > i:
        cnt += 1
      else:
        z.append((1/2)**cnt)
        break
print((1/N)*sum(z))

Submission status: Accepted

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

tmp = k
count = 0
while tmp > 1:
  tmp = tmp / 2
  count += 1

ret = 0
for i in range(1, n+1):
  goal = pow(2, count) * i
  offset = 0
  if i >= k:
    ret += (1/n)
  else:
    while goal >= k:
      goal = goal / 2
      offset += 1
    a = (1 / n) * pow(0.5, count - (offset-1))
    ret += a
print(ret)

Submission status: Accepted

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

Submission status: Accepted

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

for num in range(N):
    num = num + 1
    counter = 0
    while num < K:
        num *=2
        counter += 1
    p += 1/N * (1/2) ** counter
    
print(p)

Submission status: Accepted

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

if n > k :
    dp  = [0]*k
    prob_1 = 1/n 
    prob_2 = (n-k+1)/n
    if k % 2 == 0 :
        for i in range(k-1,0,-1) :
            if k // 2 <= i <= k-1 :
                dp[i] = 1/2 * prob_1
            else : dp[i] = dp[i*2] * 1/2
    else :
        for i in range(k-1,0,-1) :
            if k // 2 + 1/2 <= i <= k-1 :
                dp[i] = 1/2 * prob_1
            else : dp[i] = dp[i*2] * 1/2
    print("{}".format(sum(dp)+prob_2))
elif n == k : print("1")

elif  n < k :
    prob_1 = 1/n 
    prob_2 = 1 
    dp = [0]*(k)


    if k % 2 == 0 :
        for i in range(k-1,0,-1) :
            if k // 2 <= i <= k-1 :
                dp[i] = 1/2 
            else : dp[i] = dp[i*2] * 1/2
    else :
        for i in range(k-1,0,-1) :
            if k // 2 + 1/2 <= i <= k-1 :
                dp[i] = 1/2 
            else : dp[i] = dp[i*2] * 1/2
    print("{}".format(sum(dp[0:n+1])*1/n))

Submission status: Accepted

Solution code:
data = []
ans = 0
n, k = map(int,input().split())
  
for i in range(n):
  if(i+1 >= k):
    data.append(1.0/n)
  elif((i+1)%2==0):
    data.append(data[(i+1)//2-1]*2.0)
  else:
    j = 0
    while True:
      j+=1
      if(k<=(i+1)*2**j):
        break
    data.append(1.0/(n*2**j))
  
for i in range(n):
  ans += data[i]

print(ans)

Submission status: Accepted

Solution code:
#   C

import numpy as np

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

sum_poss = 0
for n in range(1, N+1):
    m0 = 0
    if n >= K:
        m0 = 0
    else:
        m0 = int(np.log2(K/n))
        if np.log2(K/n) - int(np.log2(K/n)) != 0:
            m0 += 1
#    print(m0, 1/(2**m0))
    sum_poss += 1/((2**m0)*N)
    
#sum_poss /= N


print(sum_poss)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
def main():
  input = sys.stdin.readline
  N, K =map(int,input().split())
  p = []
  for d in range(1,N+1):
    if d >= K:
      p.append(1/N)
    else:
      m = np.log2((K-1)/d)
      n = math.ceil(m)
      if m != n:
        p.append( 1/N * 1/2 ** n)
      else:
        p.append( 1/N * 1/2 ** (n+1))        
  print(sum(p))
main()

Submission status: Accepted

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

obj = [K/i for i in range(1,N+1)]
prob = 0
for i, o in enumerate(obj):
	num = 0
	m = 0
	while m < o:
		m = math.pow(2, num)
		num += 1
	prob += (1/2)**(num - 1)*(1/N)

print(prob)

Submission status: Accepted

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


for i in range(1,N+1):
    if K>i and math.floor(math.log2(K/i))!=math.ceil(math.log2(K/i)):
        count.append((1/N)*((1/2)**(1+int(math.log2(K/i)))))
    elif K>i and math.floor(math.log2(K/i))==math.ceil(math.log2(K/i)):
        count.append((1 / N) * ((1 / 2) ** (int(math.log2(K / i)))))
    else:
        no_count.append(1/N)
print(sum(count)+sum(no_count))