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: Time Limit Exceeded

Solution code:
import decimal
import math

N, K = map(int, input().split())
coin = [decimal.Decimal('0.5')**k for k in range(10**5)]
ans = 0

for i in range(1,N+1):
    tmp = decimal.Decimal(str(math.log2(K/i)))
    x = int(math.log2(K/i))
    if i >= K:
        ans += decimal.Decimal(1/N)
    else:
        if tmp - x != 0:
            x += 1
        ans += decimal.Decimal(1/N) * coin[x]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import decimal
import math

N, K = map(int, input().split())
coin = [decimal.Decimal('0.5')**k for k in range(10**5)]
ans = 0
for i in range(1,N+1):
    x = 0
    while(True):
        if i*(2**x) >= K:
            ans += decimal.Decimal(1/N) * coin[x]
            break
        else: x += 1
   

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n,k=map(int,input().split())
ans=0
for i in range(1,n+1):
  if n>=k:
    for j in range(1,k):
      cnt=math.ceil(math.log(k/i,2))
      ans+=((1/2)**cnt)*(1/n)
    for t in range(k,n+1):
      ans+=1/n
  else:
    cnt=math.ceil(math.log(k/i,2))
    ans+=((1/2)**cnt)*(1/n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K =map(int, input().split())
bordor = []
while(K >= 1):
  bordor.insert(0, K)
  K / 2
  
print(bordor)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
import math
import decimal

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

decimal.getcontext().prec = 12
N, K = lr()
answer = decimal.Decimal(0)
for x in range(1, N+1):
    power = 0
    while x < K:
        x *= 2
        power += 1
    answer += decimal.Decimal(.5) ** power

answer /= N
print('{:.12f}'.format(answer))

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
n, k = map(int,input().split())

ans = Decimal(0)
for i in range(1,n+1):
    count = 0
    if i < k-1:
        while i < k:
            i *= 2
            count += 1
    ans += Decimal(1/n) * Decimal((1/2)**count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, raw_input().split())

ans = 0
mi_prev = 0
for i in reversed(range(1, N+1)):
    for mi in range(mi_prev, K):
        if i*2**mi >= K:
            break

    ans += (1.0/2)**mi
    mi_prev = mi

ans = ans/N
print ans

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1, N+1):
    mi = 0
    for m in range(K):
        if i*2**mi >= K:
            break
        mi += 1

    ans += (1.0/2)**mi

ans = ans/N
print ans

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
print(N)
print(K)
per = 0
def f(x,y):
    count = 0
    while (x <= y):
        x = 2*x
        count += 1
    return count

for i in range(N):
    b = int(f(i,K))
    per += (1/N)((1/2)**b)
    print(per)
print(per)

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
print(N)
print(K)
per = 0
def f(x,y):
    while x < y:
        x = 2*x
    return x

for i in range(N):
    a = int(f(i,K))
    per += (1/N)((1/2)**a)
print(per)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

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

prob = Decimal(0)
for i in range(1,N+1):

    for j in range(18):
        if i*2**j >= K:
            prob += Decimal(1/2**j)
            break

print(prob/N)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

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

prob = Decimal(0)
for i in range(1,N+1):

    for j in range(20):
        if i*2**j >= K:
            prob += Decimal(1/2**j)
            break

print(prob/N)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


for x in range(N):
    bekicount = 0
    y = x
    while y < K:
        y = y*2
        bekicount = bekicount +1
    probability = probability + (x/N)*pow(0.5,bekicount)
    bekicount = 0
print(probability)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k = map(int, input().split())

two_count_list = np.array([])
for i in range(1, n+1):
    two_count =0
    score = i
    while score <= k-1:
        score *= 2
        two_count += 1

    two_count_list = np.append(two_count_list, two_count)    

print((1/n) * ((1/2) ** two_count_list).sum())

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#salmonize の文
n,k = map(int,input().split()) 
 #複数文字の入力
ans = 0     
for i in range(n+1):
  j=0
  #カウンター設置
  while i<k:
    i*=2
    j+=1
  ans=1/2**j
print("{:.12}".format(ans/n))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split()) 
 #複数文字の入力
ans = 0     
for i in range(n+1):
  j=0
  #カウンター設置
  while i<k:
    i*=2
    j+=1
  ans=1/2**j
print(ans/n)

Submission status: Time Limit Exceeded

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

ans=0
for i in range(k):
      c=0
      while i<k:
            i=i*2
            c+=1
      ans+=(1/n)*(1/2)**c
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
import decimal
decimal.getcontext().prec = 11

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

ans = decimal.Decimal(0)

for i in range(1, N+1):
    ans += decimal.Decimal(1 / N * (1 / 2) ** (max(math.ceil(math.log(K / i, 2)), 0)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul


def main():
    N, K = map(int, input().split())
    print(sum([reduce(mul, [0.5
                            for j in range(K)
                            if i << j < K], 1 / N)
               for i in range(1, N + 1)]))
    return


main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul


def main():
    N, K = map(int, input().split())
    print(sum(reduce(mul, (0.5
                           for j in range(K)
                           if i << j < K), 1 / N)
              for i in range(1, N + 1)))
    return


main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
n,k = map(int, input().split())
ttl = 0
res = []
for i in range(1,n+1):
  ttl = i
  cnt = 0
  while True:
    if ttl >= k:
      break
    ttl = ttl*2
    cnt+=1
  p = Fraction(1,n)*Fraction(1,2)**cnt
  res.append(p)
ans = sum(res)
print(float(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
n,k = map(int, input().split())
ttl = 0
res = []
for i in range(1,n+1):
  ttl = i
  cnt = 0
  while True:
    if ttl >= k:
      break
    ttl = ttl*2
    cnt+=1
  res.append(cnt)
ans = sum([Fraction(1,n)*Fraction(1,2)**e for e in res])
print(float(ans))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
pb = 0
count = 0
if n >= k:
  pb += (n-k+1)/n
  count = k - 1
else:
  count = n
 
for i in range(1, count+1):
  mul = 0
  while k > i ** mul:
    mul += 1
  pb = pb +  (1/n) * (1 / (2**mul))
print(pb)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
sum=0
while(1):
  for i in range(1,N+1):
    tmp=1/N
    now=i
    while(K>now):
      now*=2
      tmp/=2
    sum+=tmp
print(sum)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=[]
i=0
while len(a)==0 or a[-1]!=1:
    a.append((k-1)//(2**i))
    i+=1
n1=len(a)
if n>=k:
    s=(n-k+1)/n
    for i in range(n1):
        if i!=n1-1:
            s+=(a[i]-a[i+1])/(n*(2**(i+1)))
        else:
            s+=a[i]/(n*(2**(i+1)))
else:
    s=0
    for i in range(n1):
        if i!=n1-1 and a[i]>=n>a[i+1]:
            s+=(n-a[i+1])/(n*(2**(i+1)))
        elif i!=n1-1 and n>a[i+1]:
            s+=(a[i]-a[i+1])/(n*(2**(i+1)))
        elif n>=a[i]:
            s+=a[i]/(n*(2**(i+1)))
print(s)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import random

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

# 10^10回試行して
# そのうち該当する試行回数を計測する
# →確率計算


trial = 1

for i in range(10):
    trial *= 10

#print(trial)

for i in range(trial):

    N_dice = random.randint(1, N)
    coin = random.randint(0, 1)

    score_now = N_dice

    true_case = 0
    all_case = 10 ^ 10

    while(1 <= score_now <= K-1):
        if(coin == 1):
            score_now *= 2
        if(coin == 0):
            #print('Break')
            break
        true_case += 1

prob = true_case / trial
print(prob)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

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

p = 0
for i in range(n):
    j = i + 1
    t = 0
    while j < k:
        j **= 2
        t += 1
    p += ((1/2)**t)/n

print(p)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
C - Dice and Coin
https://atcoder.jp/contests/abc126/tasks/abc126_c
 
"""
import sys
 
 
from decimal import *
from math import log2, ceil
 
def solve(N, K):
    getcontext().prec = 12
    ans = Decimal(0)
    for i in range(1, N+1):
        if i >= K:
            t = Decimal (1/N)
        else:
            t = Decimal(1/N/2**ceil(log2(K/i)))
        ans += t
    return ans
 
 
def main(args):
    N, K = map(int, input().split())
    ans = solve(N, K)
    print(ans)
 
 
if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
N, K = map(int, input().split())
F = []

for i in range(1, N + 1):
    point = i
    j = 0
    while point < K:
        point *= 2
        j += 1
    F.append(Fraction(1, N) * (Fraction(1, 2) ** j))

print(float(sum(F)))

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
N , K=map(int, input().split())

F = []

for i in range(1,N + 1):
    point = i
    j = 0
    while True:
        if point >= K:
            break

        point *=  2
        j += 1
    F.append(Fraction(1, N) * (Fraction(1,2) ** j))

print(float(sum(F)))

Submission status: Time Limit Exceeded

Solution code:
import decimal


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


main()

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

n, k = map(int, input().split())
sum = Decimal(0.0)
for i in range(1, n + 1):
    p = Decimal(1.0 / n)
    score = i
    while score < k:
        score = score * 2
        p = p * Decimal(0.5)
    sum += p
print(str(sum)[:14])

Submission status: Time Limit Exceeded

Solution code:
#   C

import numpy as np

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

sum_poss = 0
for n in range(1, N+1):
    m = 0
    poss = 1
    while n*2**m < K:
        m *= 2
        poss /= 2
    sum_poss += poss/N
    
#sum_poss /= N


print(sum_poss)

Submission status: Time Limit Exceeded

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

P = 0
for i in range(1, N+1):
    if i < K:
        cnt = 0
        X = 0
        while True:
            X = i*2
            cnt += 1
            if X >= K:
                P += 1/2**cnt + 1/N
                break
    else:
        P += 1/N

print(P)

Submission status: Time Limit Exceeded

Solution code:
inp = input().split()
inp = [int(s) for s in inp]

X = 0.0
if 1 - (inp[1] + 1) / inp[0] > 0:
    X = 1.0 - (inp[1] + 1) / float(inp[0])

i = inp[1]
c = 0
while i < inp[0]:
    i = int((float(i) / 2) + 0.5)
    c = c + 1

X += (inp[0] - i) * (0.5 ** c) / float(inp[0])
while i / 2 > 0:
    i = int((float(i) / 2) + 0.5)
    c = c + 1
    X += (i - (float(i) / 2 + 0.5)) * (0.5 ** c) / float(inp[0])

print(X)

Submission status: Time Limit Exceeded

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 = 1
        while K > s:
            s *= 2
            c /= 2
        ans += decimal.Decimal((1 / N) * c)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
N, K = map(int, input().split())
point = 0
percent = Decimal(0)
for n in range(N):
    point = n + 1
    count = 0
    per = Decimal(1/N)
    while point < K:
        point *= 2
        count += 1
    percent += Decimal(per)*Decimal(1/(2**count))
    point = 0

print(Decimal(percent))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from fractions import Fraction
def main():
    N,K = map(int,input().split())
    countlist = []
    answer = 0
    print(N,K)
    for i in range(N):
        count = 0
        while i <= K-1:
            i += i*2
            count +=1
        countlist.append(count)
    print(countlist)
    for j in countlist:
        answer += Fraction(1,N) * Fraction(1,2)**j
    print(answer)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
E=[]
for i in range(N):
  pN = i
  j = 0
  while pN<=K-1:
    pN=pN*(2**j)
    j+=1
    e = (1/N)*(1/2)**j
    E.append([e])

print(sum(E))

Submission status: Time Limit Exceeded

Solution code:
import decimal


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


main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from fractions import Fraction
def main():
    N,K = map(int,input().split())
    countlist = []
    answer = 0
    for i in range(N):
        count = 0
        while i <= K-1:
            i = i*2
            count +=1
        countlist.append(count)
    for j in countlist:
        answer += Fraction(1,N) * Fraction(1,2)**j
    print(answer)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
if N>K:
    ans=(N-K+1)/N
else:
    ans=0
for j in range(N):
    l=j
    m=0
    if j==0:
        pass
    while l<K:
        l=2*j
        m+=1
    else:
        ans+=(1/N)*1/(2**m)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

array = []
for i in range(N):
    n = i+1
    nankai = 0
    while n < K:
        n*2
        nankai += 1
    array.append(nankai)

kakus = 0
for k in array:
    kaku = (1/N)
    for q in range(k):
        kaku * (1/2)
    kakus += kaku

print(kakus)

Submission status: Time Limit Exceeded

Solution code:

N,K =map(int,input().split())
n = 0
ans = 0
L = K-1
R = N
while True:
    if L < N:
        break
    else:
        n += 1
        R = L
        L = R//2

if R > N:
    R=N

while True:
    foo = R-L
    foo /= 2**n
    ans += foo
    if L==1:
        ans += 1/(2**(n+1))
        break
    R = L
    L =R//2
    n += 1
print(ans/N)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction

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

prob = 0

for i in range(1, N+1):
    j = i
    num_omote = 0
    while j < K:
        j *= 2
        num_omote += 1
    prob += Fraction(1, N) * Fraction(1, 2)**num_omote

print(float(prob))

Submission status: Time Limit Exceeded

Solution code:
import decimal

N, K = map(int, input().split())
n = decimal.Decimal(N)
result = decimal.Decimal(0.00000000000)

def check(i, K):
    count = 0
    while (K > i):
        i *= 2
        count += 1
    return count

for i in range(1,N+1):
    count = check(i, K)
    dec = decimal.Decimal(1.00000000000)
    for j in range(count):
        dec /= decimal.Decimal(2.00000000000)
    result += dec

print(result/n)

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
N, K = map(int, input().split())

ans = Decimal(0)
if K <= N:
    ans += Decimal(max(N-K+1, 0))/Decimal(N)
thres = N+1
if K <= N:
    thres = K

for i in range(1, thres):
    p = Decimal(1/N)
    score = Decimal(i)
    while score < K:
        score = score * Decimal(2)
        p = p / Decimal(2)
    ans = ans + p

print(ans)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
cal=0
for i in range(1,n+1):
  for j in range(100000):
    if i*2**j<k and i*2**(j+1)>=k:
      cal+=(1/2)**(j+1)
      break
print(cal/n)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
C - Dice and Coin
https://atcoder.jp/contests/abc126/tasks/abc126_c

"""
import sys


from decimal import *
from math import log2, ceil


def solve(N, K):
    getcontext().prec = 30
    ans = Decimal(0)
    for i in range(1, N+1):
        if i >= K:
            t = Decimal (1/N)
        else:
            t = Decimal(1/N/2**ceil(log2(K/i)))
        ans += t
    return ans


def main(args):
    N, K = map(int, input().split())
    ans = solve(N, K)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
C - Dice and Coin
https://atcoder.jp/contests/abc126/tasks/abc126_c

"""
import sys


from decimal import *
from math import log2, ceil

def solve(N, K):
    getcontext().prec = 50
    ans = Decimal(0)
    for i in range(1, N+1):
        if i >= K:
            t = Decimal (1/N)
        else:
            t = Decimal(1/N/2**ceil(log2(K/i)))
        ans += t
    return ans


def main(args):
    N, K = map(int, input().split())
    ans = solve(N, K)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
N, K = map(int, input().split())
ans = 0
for n in range(1, N + 1):
    c = 0
    while n < K:
        n = n << 1
        c += 1
    t = 1 << c
    ans += Decimal("1.0") / Decimal(str(N * t))
print(ans)

Submission status: Accepted

Solution code:
import math
N, K = map(int, input().split())
ans = 0
for i in range(1, N+1):
    b = math.ceil(K / i-1).bit_length()
    ans += 1/pow(2, b)
print(ans/N)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N,K = map(int, input().split())
ans = 0
for n in range(1, N + 1):
    cnt = 0
    sums = n
    while sums < K:
        sums *= 2
        cnt += 1
    ans += 0.5 ** cnt
print(ans/N)

Submission status: Accepted

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

print(sum(prob))

Submission status: Accepted

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

print(sum(prob))

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

ans = 0

for i in range(1,n+1):
  p = i
  r = 1
  while p < k:
    p*=2
    r/=2
  ans+=r

ans/=n

print(ans)

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
import collections
import itertools

def main():
    n, k = input_list()
    res = 0.0
    for v in range(n):
        i = v + 1
        t = 1.0
        ii = i
        while ii < k:
            ii *= 2
            t /= 2.0
        res += t

    res /= n
    print(res)


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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def solve(N: int, K: int):
    ans = 0
    for n in range(1, N+1):
        b = 1
        while n * b < K:
            b <<= 1
        ans += 1 / (b * N)
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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
    print(solve(N, K))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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

per = 0

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

print(per)

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/N*0.5**(math.ceil(math.log2(K/i)))
  else:
    ans+=1/N
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

if k == 1:
    print(1)
    sys.exit(0)

# 場合分けをする必要はなかった
#if k <= n:
#    ans = ((n - k) + 1) / n
#    upper = k - 1
#else:
#    ans = 0
#    upper = n
#for i in range(1, upper + 1):
#    tmp = 1 / n
#    while i < k:
#        tmp *= (1 / 2)
#        i *= 2
#    ans += tmp
ans = 0
for i in range(1, n + 1):
    tmp =  1 / n
    while i < k:
        tmp *= (1 / 2)
        i *= 2
    ans += tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

if k == 1:
    print(1)
    sys.exit(0)

if k <= n:
    ans = ((n - k) + 1) / n
    upper = k - 1
else:
    ans = 0
    upper = n
for i in range(1, upper + 1):
    tmp = 1 / n
    while i < k:
        tmp *= (1 / 2)
        i *= 2
    ans += tmp
print(ans)

Submission status: Accepted

Solution code:


def main():
    n, k = map(int, input().split())
    ans = 0.0
    for t in range(1, n + 1):
        cnt = 0
        now = t
        per = 1.0
        while now < k:
            per /= 2
            now *= 2
        ans += per / n
    print('{:.20}'.format(ans))
    pass


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

[N,K] = list(map(int,input().split()))

nino_ijo=[0]*21
for i in range(21):
    nino_ijo[i] = 2**i
# print('nino:', nino_ijo)

out=0
for i in range(1,N+1):
    # print('i:',i)
    for j in range(21):
        if i*(2**j) >= K:
            out += (1/N) * ((1/2)**j)
            break
    # print('out:',out)
print(out)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#ABC126 C

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

Submission status: Accepted

Solution code:
def abc126c():
    import math
    n, k = map(int, input().split())
    ans = 0.0
    for i in range(1, n + 1):
        v = max(0, math.ceil(math.log2(k / i)))
        ans += math.pow(0.5, v)
    print(ans/n)


abc126c()

Submission status: Accepted

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

# pows[i] = pow(2, i)
pows = [1]
while pows[-1] < k:
    pows.append(2 * pows[-1])

ans = 0
ind = -1
for i in range(1, n + 1):
    if -ind < len(pows) and pows[ind-1] * i >= k:
        ind -= 1
    ans += pows[-ind - 1]

print(ans / (pows[-1] * n))

Submission status: Accepted

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

# 何回2をかけると超えるか。
def func1(i, k):
    ans = 0
    num = i
    end = False
    if num >= k:
        return 0
    while(not end):
        ans += 1
        num *= 2
        if num >= k:
            end = True
            break
    return ans


ans = 0
for initial_score in range(1, N+1):
    ans += (1/N) * (1/2) ** func1(initial_score, K)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = 1
ans = 0



while (A <= N):
  count = 0
  T = A
  while (T<K):
    T = T*2
    count += 1
  ans += float((1/N)*(1/2)**count)
  A += 1
  
print(ans)

Submission status: Accepted

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

ans = 0

for i in range(1,n+1):
    if i>=k:
        ans += (1/n)
        continue
    x = 1
    while 1:
        i *= 2
        if i>=k:
            break
        else:x+=1
    ans += (1/n)*(1/2)**x
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

import math

prob = 0
for i in range (1, N+1):
	if i>=M:
		prob+=1/N
	else:
		prob+=((1/N)*1/2**math.ceil(math.log(M/i, 2)))

print(prob)

Submission status: Accepted

Solution code:
from math import *

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

ans = 0
for i in range(1, n+1):
  tmp = 1 / n
  if i < k:
    tmp *= 0.5 ** ceil(log2(k/i))
  ans += tmp

print(ans)

Submission status: Accepted

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

sum : float = 0.0
for i in range(1,n+1):
    ret : float = 1/n
    tmp = i
    while(tmp < k):
        tmp *= 2
        ret /= 2
    if(tmp != 0):
        sum += ret 
print(sum)

Submission status: Accepted

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

import math

ans = 0
for i in range(1, n+1):
    if i < k:
        power = math.ceil(math.log2(k/i))
    else:
        power = 0
    ans += pow(0.5, power)
print(ans / n)