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:
from math import log, ceil
N, K = [int(n) for n in input().split()]
ans = 0
for i in range(1, N+1):
    tmpans = ceil(log(K/i, 2))
    # print(i, tmpans)
    if tmpans < 0:
        ans += 1/N
    else:
        ans += 1/N * (1/2)**tmpans
print(ans)

Submission status: Accepted

Solution code:
import math

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

ret = 0
for x in range(1, N + 1):
    if K <= x:
        ret += 1
    else:
        ret += 0.5 ** math.ceil(math.log2(K / x))
print(ret / N)

Submission status: Accepted

Solution code:
import math
 
N, K = map(int, input().strip().split(' '))
 
ans = 0
count = int(math.log(K,2)-math.log(N,2))
if count < 0:
    count = 0
val = 2**count
 
for n in range(N, 0, -1):
    while n*val < K:
        val *= 2
        count *= 2
    #print('COUNT=', count)
    ans += 1.0/val
 
print(ans/N)

Submission status: Accepted

Solution code:
###
### atcorder test program
###

import sys
import math

### math class
# class math:
#     ### pi
#     pi = 3.14159265358979323846264338

#     ### GCD
#     def gcd(self, a, b):
#         if b == 0:
#             return a
#         return self.gcd(b, a%b)

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

# math = math()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]
#R = float(input())
#A = [int(x) for x in input().split()]
#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

### output sample
#print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
#print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
#print(" {}".format(i), end="")

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

probability = 0

for i in range(1,N+1):
    score = i
    count = 0
    while score < K:
        count += 1
        score *= 2
    probability += (0.5**count)/N
    #print(i,count,probability)

print("{:.12f}".format(probability))

Submission status: Accepted

Solution code:
import math

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

prob = 0

if n < k:
    for  i in range(1, n+1):
        prob += 0.5**math.ceil(math.log2(k/i)) * (1/n)
    print(prob)
else:
    for  i in range(1, k):
        prob += 0.5**math.ceil(math.log2(k/i)) * (1/n)
    print(prob + (n-k+1)/n)

Submission status: Accepted

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

import math

N, K = LI()

p = 0
for a in reversed(range(1,N+1)):
    if a >= K:
        p += 1/N
    else:
        p += (1/N) * (0.5)**math.ceil(math.log2(K/a))

print(p)

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
prob = 0.0
for i in range(1,N+1):
    count = 0
    powerdice = i
    while(powerdice<K):
        powerdice *= 2; count+=1
    prob+= 1.0/(2**count)

print("{:.12f}".format(prob/N))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

N, K = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

Cnt=[0]*(N+1)
A=[0]*(N+1)

for iDice in range(1,N+1):
	i=0
	while iDice * (2**i) < K:
		i+=1
	
	Cnt[iDice]=i
	A[iDice]=((1/2)**i)/N

print(sum(A))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
if k<=n:
    ans = float((n-k+1)/n)
else:
    ans = 0
c = float(1/n)
for i in range(1,min(k,n+1)):
    num = i
    cnt = 0
    while num<k:
        num*=2
        cnt += 1
    ans += c*float((0.5)**cnt)
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:
        n = ceil(log2(K/i))
        ans += (1/N) * (1/2)**n
    else:
        ans += 1/N
print(ans)

Submission status: Accepted

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

answer = 0
for dice in range(n+1)[1:]:
    if dice < k:
        power = math.ceil(math.log2(k/dice))
    else:
        power = 0
    answer += (1/n)*(1/2**power)
print(answer)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ans = max((n - k + 1) / n, 0)
for a in range(1, min(k, n + 1)):
    cnt = 0
    while k > a:
        a *= 2
        cnt += 1
    ans += 0.5 ** cnt / n
print('{:.12f}'.format(ans))

Submission status: Accepted

Solution code:
import math

n,k=[int(i) for i in input().split()]
l=[]
for i in range(n):
    j=math.ceil(math.log2(k/(i+1)))
    l.append(2**j*n if j > 0 else 1*n)
print(sum([1/i for i in l]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K = [int(i) for i in input().split()]
P = 0
def nPossibility(n):
    c = 0
    while K > n:
        n = n*2
        c += 1
    return 1/(2**c)
for i in range(1,N+1):
    P += (1/N)*nPossibility(i)
print(P)

Submission status: Accepted

Solution code:
import math

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

ans = 0.0
for i in range(1, n+1):
    if i > k:
        ans += 1.0
    else:
        temp = math.log2(k / i)
        if abs(temp - int(temp)) > 0.0000000001:
            temp = int(temp) + 1
        ans += (0.5 ** temp)
ans = ans / n
print(ans)

Submission status: Accepted

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

def alg(x,K):
  num = 0
  while x < K:
    num += 1
    x = x*2
  return num

ans = 0
for i in range(1,N+1):
  ans += (1/N) * (1/2)** alg(i,K)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

print (ans)

Submission status: Accepted

Solution code:
import math

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

bunshi = 0
bumbo = 2 ** math.ceil(math.log(k, 2)) * n

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

print(bunshi / bumbo)

Submission status: Accepted

Solution code:
from math import ceil
n,k=map(int,input().split())
b=k
p=0
pp=1
nn=n
while b>0:
    c = max(nn-b+1,0)
    z = c/(n*pp)
    p += z
    pp *= 2
    nn = min(b-1, nn)
    if b == 1:
        b = 0
    else:
        b = ceil(b/2)
print(p)

Submission status: Accepted

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

ans = 0

for i in range(N):
  point = i+1
  prob = 1/N
  while(point <= K - 1):
    point = point*2
    prob = prob*0.5
  ans += prob

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
import math
i=0
p=n
Sum=0
while not p==0:
    if k>n:
        k=math.ceil(k/2)
        i=i+1
    else:
        Sum=Sum+(p-k+1)*((0.5)**i)/n
        p=k-1
        k=math.ceil(k/2)
        i=i+1
print(Sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, k = map(int, input().split())

p=0
for i in range(n):
  count = 0
  while k/(i+1)>2**count:
    count = count+1
  p = p + (1/2)**count/n
print(p)

Submission status: Accepted

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: Accepted

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

ans = 0.0
for n in range(1,N+1):
	judge = 0
	k_min = 0
	while judge == 0:
		if n*(2**k_min) >= K:
			judge = 1
		else:
			k_min += 1
	ans += 1.0/(N*(2**k_min))
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ans = 0
# Dice
p_d = 1 / N
lst_dice = [int(i) + 1 for i in range(N)]
# Coin
p_c = 1 / 2


for p in lst_dice:
    j = 0
    while 2**j < K / p:
        j += 1
    # print(j)
    p_tmp = p_d * (1 / 2) ** j
    ans += p_tmp


print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

ary = np.log2(k / (np.arange(n)+1))
ary = np.ceil(ary)

ary[ary < 0] = 0

prob = (1 / 2**ary).sum().astype(np.float64) / len(ary)
print(prob)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
nk = input().split()
res = 0
init_probability = 1 / int(nk[0])

for i in range(int(nk[0])):
    thisRes = init_probability
    deme = i + 1
    while(1):
        if(deme >= int(nk[1])):
            break
        thisRes /= 2
        deme *= 2
    res += thisRes
print(res)

Submission status: Accepted

Solution code:
import math

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

p = 0.0
if N < K:
    for i in range(1, N+1):
        p += math.pow(0.5, math.ceil(math.log2(K/i)))/N
else:
    for i in range(1, K+1):
        p += math.pow(0.5, math.ceil(math.log2(K/i)))/N
    p += (N-K)/N    

print(p)

Submission status: Accepted

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

def l2c(x):
	c = 1 / n
	while x < k:
		x = x * 2
		c = c / 2
	return c

print(sum([l2c(i) for i in range(1, n+1)]))

Submission status: Accepted

Solution code:
import math
N, K = map(int, input().split())
lis = [0 for i in range(N)]

i = 0
p = 1
ans = max(N-K +1,0)
while K:
  p/=2
  last = K
  K = math.ceil(K/2)
  cnt = max(min(last,N+1)- K , 0)
  ans += cnt * p
  if K ==1:
    break
    
print(ans/N)

Submission status: Accepted

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

p = 0
uncounted = n

for i in range(18):
    lb = ceil(k * 2 ** -i)
    if lb <= uncounted:
        p += (uncounted - lb + 1) * 2 ** -i
        uncounted = lb - 1
        
print(p / n)

Submission status: Accepted

Solution code:
#Xの目が出た時、1/2のceil(log2(K/X))乗の確率でうまくいく
import math
N,K=map(int,input().split())
print(sum([
    (1/2)**max(0,math.ceil(math.log2(K)-math.log2(x)))
    for x in range(1,N+1)])/N)

Submission status: Accepted

Solution code:
def prob(N, K):
    prob = .0

    for n in range(1, N + 1):
        tmp_prob = 1. / N
        while (n < K):
            tmp_prob *= .5
            n *= 2

        prob += tmp_prob

    return prob


if __name__ == '__main__':
    N, K = map(int, input().split())
    prob = prob(N, K)
    print(prob)

Submission status: Accepted

Solution code:
import math

def main():
    N,K = map(int, input().split())
    prob = 0
    for a in range(N):
        power = math.ceil(max(0,math.log2(K)-math.log2(a+1)))
        prob += ((0.5)**power)
    print(prob/N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
input = sys.stdin.readline

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

for saikoro in range(1, n + 1):
    if(saikoro < k):
        kaisu = math.ceil(math.log2(k / saikoro))
        kakuritu += 2 ** (-1 * kaisu)
    else:
        kakuritu += 1

print(kakuritu/n)

Submission status: Accepted

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

    
print(ans)

Submission status: Accepted

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

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

print(round(sum(l), 12))

Submission status: Accepted

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

for i in range(n):
    dif = k - i
    temp = i + 1
    count = 0

    while (temp < k):
        #print(temp)
        temp = temp * 2
        count += 1

    p = (1 / n) * (1 / 2) ** count
    res += p

print(res)

Submission status: Accepted

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

halfs = []
tar = 1
for i in range(1,20):
    tar /= 2.0
    halfs.append(tar)

res = 0
for i in range(1,N + 1):
    if i < K:
        tmp = i
        index = 0
        while tmp < K:
            tmp *= 2
            index += 1
        res += halfs[index - 1] * float(1.0 / N)
    else:
        res += float(N - K + 1) / N
        break

print(res)

Submission status: Accepted

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

Submission status: Accepted

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

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

print(H)

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split(" ")]
sum = 0.0

def fank(n, k, i):
  kaku = 1 / n
  while k > i:
    i = i * 2
    kaku = kaku * 0.5
  return(kaku)

for i in range(N):
  sum += fank(N, K, i + 1)

print(sum)

Submission status: Accepted

Solution code:
from math import log2


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


N, K = inpl()

bunshi = 0
for i in range(1, N + 1):
    if i >= K:
        bunshi += (N - i + 1) * (2**17)
        break

    tmp = log2(i) - log2(K)
    X = abs(tmp // 1)
    bunshi += 2**(17 - X)

print('{:.15f}'.format(bunshi / (N * (2**17))))

Submission status: Accepted

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

print(sum)

Submission status: Accepted

Solution code:
import math

def main():
    n, k = [int(x) for x in input().split()]
    p = 0
    for i in range(n):
        dice = i + 1
        if dice >= k:
            p += 1
        else:
            p += 0.5 ** (math.ceil(math.log2(k / dice)))
    p /= n
    print(p)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K  = list(map(int, input().split()))
p_sum = 0.0
for i in range(1, N + 1):
    score = i
    counter = 0
    while 1 <= score and score <= K - 1:
        score = score * 2
        counter += 1
    p = (0.5 ** counter) / N
    p_sum += p
print(p_sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

N, K = list(map(int, input().split()))
x = 1/N
ans = 0

for i in range(1, N+1):
    if i < K:
        n = math.ceil(math.log2(K/i))
        ans += (x * 0.5**n)
    else:
        ans += x

print(ans)

Submission status: Accepted

Solution code:
import math

n,k = (int(x) for x in input().split())

temp = 0
for i in range(1,n+1):
    x = math.ceil(math.log2(k/i))
    #print(x)
    if x<0:
        x=0
    temp += 1/2**x
    
print(temp/n)

Submission status: Accepted

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

if k <= n:
  prob = 1 - (k-1)/n
else:
  prob = 0

p = 1 - prob
for i in range(1, min(k, n+1)):
  prob += 0.5 ** math.ceil(math.log2(k/i)) / n

print(prob)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

win = 0
for n in range(1, N + 1):
    if n < K:
        hoge = ((1 / 2) ** math.ceil(math.log(K,2) - math.log(n,2))) * (1/N)
    else:
        hoge = 1/N
    win += hoge
print(win)

Submission status: Accepted

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

N = int(N)
K = int(K)

prob = 0.
for i in range(1, N+1):
    if i >= K:
        prob += (N-i+1)/N
        break
    else:
        c = 0
        while i < K:
            i = i*2
            c += 1
        prob += (1./N) * (.5**c)

print("%.10f" % prob)

Submission status: Accepted

Solution code:
import math

n,k=map(int, input().split())
omote = [math.ceil(math.log2(k/(i+1))) for i in range(n)]
ans = 0
for r in omote:
    if r>0:
        ans += 2 ** (-r)
    else:
        ans += 1
print(ans/n)

Submission status: Accepted

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

Submission status: Accepted

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

s = 0
d = 1 / n
for i in range(1, n+1):
    if i >= k:
        s += d
    else:
        a = math.ceil(math.log2(k / i))
        s += d * pow(0.5, a)
print(s)

Submission status: Accepted

Solution code:
import math
n,k = map(int, input().split())
ans = 0
exp = 1
right = n
while right > 0:
  left = math.ceil(k / exp)
  ans += max(right - left+1,0) / (exp * n)
  right = min(left-1,n)
  exp *= 2
print(ans)

Submission status: Accepted

Solution code:
# p = 1 / N
# a * 2^b >= K
#
# b >= log2(K / a)
#
# [b]回表になる確率
# sum p * (1/2)^[b]

import numpy as np

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

a = np.arange(N) + 1
b = np.log2(K / a)
b_ = np.ceil(b)
b_[b_ < 0] = 0

s = np.sum(0.5 ** b_) / N
print(s)

Submission status: Accepted

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

s = 0
cnt = [2**20 if 1 <= i <= n else 0 for i in range(100002)]
for i in range(1, k):
    if 2 * i < k:
       cnt[2 * i] += cnt[i] // 2
       cnt[0] += cnt[i] // 2
       cnt[i] = 0
    else:
       cnt[-1] += cnt[i] // 2
       cnt[0] += cnt[i] // 2
       cnt[i] = 0
ans = 1.0 - cnt[0] / (n * 2**20)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np


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

b =  k
a = n + 1
d = a - b
s = 0
i = 0
recs = []


while (a!=1):
    d = a - b
    if d >= 0:
        s += (d * 0.5 ** i)
        a = b
        recs.append([d, i])
#     print(a, b, i, d, s)
    b = b//2 + b%2
    i += 1
ans  = s/n

print(ans)

Submission status: Accepted

Solution code:
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g

n,k = map(int,input().split())
twices = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072]

base = 0
for i in range(len(twices)):
    if k <= twices[i]:
        base = i
        break


head = 0
for i in range(1,n+1):
    temp = 0
    if k%i == 0:
        temp = k//i
    else:
        temp = k//i+1
    #print(temp)
    for j in range(len(twices)):
        if temp <= twices[j]:
            head += 2**(base-j)
            #print(i,j,2**(base-j))
            break
#print(2**base)
print(head/((2**base)*n))
"{:.2f}".format(3.141592)

Submission status: Accepted

Solution code:
import math

def solve():
    N, K = map(int, input().split())
    result = 0
    for i in range(1, N + 1):
        cn = 0
        if i >= K:
            cn = (1 / N)
        else:
            cn = (1 / N) * ((1 / 2) ** math.ceil(math.log2(K / i)))
        # print(i, '得点の時:', cn)
        result += cn
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
N, K = map(int, input().split())
chance = 0
for i in range(1,N+1):
    temp = i
    counter = 0
    if(i<K):
        while(True):
            temp *= 2
            counter += 1
            if(temp >= K):
                break
    chance += ((1/N)*math.pow(1/2,counter))
print(chance)

Submission status: Accepted

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

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

_k = 0
_count = 0
_ans = 0

for i in range(1,N+1):
    _k = i
    _count = 0
    while _k < K:
        _k *= 2
        _count += 1

    _ans += float(1)/N*float(1)/2**_count

print _ans

Submission status: Accepted

Solution code:
import numpy as np
words = lambda t : list(map(t, input().split()))

n, k = words(int)

ans = 0
for i in range(1,n+1):
    if i < k:
        t = (1/n) * (1/2)**(np.ceil(np.log2(k/i)))
    else:
        t = (1/n)
    #print(i, t)
    ans += t

print(ans)

Submission status: Accepted

Solution code:
import math

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

sum = 0.0
for x in range(1, N+1):
    if x < K:
        m = math.ceil(math.log2(float(K) / float(x)))
    else:
        m = 0.0
    sum += (1.0 / float(N)) * ((0.5) ** m)

print(sum)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 126
# https://atcoder.jp/contests/abc126
import sys
import math
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, K = i2nn()
    ans = max((N - K + 1) / N, 0)
    n = min(N, K - 1)
    l = 1
    r = 1.0
    while True:
        if n <= 0:
            break
        l *= 2
        r *= 0.5
        d = n * l - (K-1)
        if d > 0:
            d2 = math.ceil(d / l)
            ans += (d2 / N) * r
            n -= d2
    print(ans)

main()

Submission status: Accepted

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


def solve(N: int, K: int):
    b1 = math.log2(K)

    p = 0
    for n in range(1,N+1):
        b2 = math.log2(n)
        c  = max(math.ceil(b1-b2),0)
        p  += 0.5**c

    print(p/N)
        


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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 = map(int,input().split())


P = 0
for i in range(1,N+1,1):
    count = 0
    I=i
    while(I<K):
        I*=2
        count +=1
    
    coin_n = count
    P += (0.5**coin_n)

P/= N
print(P)

Submission status: Accepted

Solution code:
import math

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

prob = 0
for i in range(1, N+1):
    k = math.log2(K/i)
    if k != int(k):
        k = int(k) + 1

    if i >= K:
        prob += 1/N
    else:
        prob += 1/N * (1/2)**k

print(prob)

Submission status: Accepted

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

ans = 0
for n in range(N):
    s = n+1
    p = 1/N #ダイスの確率
    
    if s>=K:
        ans += p
    else:
        count = 0
        while s < K:
            count += 1
            s = s*2
            p = p/2
        ans += p
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

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



print(ans)

Submission status: Accepted

Solution code:
import math
N, K = map(int, input().split())
right=N
left=K
ans=0
cnt=0
while left > N:
    left = math.ceil(left/2)
    cnt+=1
while True:
    ans += (1/N)*(right-left+1)*(1/2)**cnt
    right = left-1
    left = math.ceil((right+1)/2)
    cnt+=1
    if left==1:
        break
ans += (1/N)*(right-left+1)*(1/2)**cnt
print(ans)

Submission status: Accepted

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

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

print(p)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	N, K = map(int, input().split(" "))
	#S = input()
	#S = S[:-1]
	#S = list(S)

	sel = []
	for i in range(1, N+1):
		tmp = i
		counts = 0
		while True:
			if tmp >= K:
				break
			tmp *= 2
			counts += 1
		sel.append(counts)

	ans = 0
	for i, val in enumerate(sel):
		ans = ans + ((1/N) * ((1/2)**val))

	print(ans)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import math

n, k = input().split()

n = int(n)
k = int(k)

total_p = 0

for i in range(n):
    i = i + 1  # i = 1 ~ n
    if k <= i:
        total_p += 1
    else:
        ntimes = math.ceil(math.log2(k / i))
        total_p += 1 / (2**ntimes)

p = total_p / n

print('{:.12f}'.format(p))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from fractions import Fraction

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

def nextOrd2(target):
    for i in range(20):
        if 2 ** i >= target:
            return i

ans = Fraction(0, 1)

for i in range(1, N+1):
    p = nextOrd2(K/i)
    ans += Fraction(1, N * 2 ** p)

print('{:.11f}'.format(ans.numerator/ans.denominator))

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(len(cnt)):
    sumans += (1/2)**cnt[i]

print((1/N) * sumans if N < K else (N-K)/N + (1/N)*sumans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n, k = get_li()
    d = dict()
    t = n
    v = k
    m = 0
    while v > 1:
        if v < t:
            d[m] = t - int(ceil(v)) + 1
        m += 1
        t = min(t, int(ceil(v)) - 1)
        v = k / (2 ** m)
    d[m] = t - int(ceil(v)) + 1
    ans = 0
    for k, v in d.items():
        ans += v / (n * (2 ** k))
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

exp = 0

def calc_exp(init) :
	point = init
	n_play = 0

	while point < K :
		point *= 2
		n_play += 1

	return 1 / (2 ** n_play)

for i in range(1, N+1) :
	exp += calc_exp(i)

print('{:.10f}'.format(exp / N))