Problem:


Score : 300 points

Problem Statement

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

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

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

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

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

Constraints

1 ≤ N ≤ 10^5

1 ≤ K ≤ 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

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

Sample Input 1

3 10

Sample Output 1

0.145833333333

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

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

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

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

Sample Input 2

100000 5

Sample Output 2

0.999973749998



Sample input:
3 10


Sample output:
0.145833333333

Submission status: Accepted

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

p_sum = 0.0
point = 0

for i in range(1, n+1):
    point = i
    p = 1.0

    # print('*** n:{}'.format(i))

    while True:
        if point >= k:
            p_sum += p * (1.0/n)
            # print('p_sum:{}'.format(p_sum))
            break

        p = p * 0.5
        point = point * 2

print(p_sum)

Submission status: Accepted

Solution code:
N, k=map(int, input().split())
flag=0
if N>=k:
    NN=N-k+1
    M=k-1
    flag=1
else:
    M=N
if M==0:
    print(1/1)
    exit(0)
lls=[]
l=1
while True:
    if 2**l >=k:
        break
    else:
        l+=1
lls.append(l)
if M>=2:
    for s in range(2,M+1):
        for i in range(l,-1,-1):
            if 2**i <k/s:
                lls.append(i+1)
                break
s=0
for i in range(len(lls)):
    s+=0.5**lls[i]
print(s/N if flag==0 else (s+NN)/N)

Submission status: Accepted

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

for i in range(1, n+1):
    t = i
    rate = 10000
    while t < k:
        t *= 2
        rate *= 0.5
    # rate: 勝利確率
    ans += rate

print(ans/n/10000)

Submission status: Accepted

Solution code:
import numpy as np
n,k=map(int,input().split())
s=np.arange(n)+1
s=k/s
s=np.ceil(np.log2(s))
s=np.power(0.5,s)
s=np.where(s<1,s,1)
s=np.sum(s)/n
print(s)

Submission status: Accepted

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

if N < K:
    for i in range(1,N+1):
        tmp = i
        tmp_prob = 1.0/N
        while tmp < K:
            tmp = 2 * tmp
            tmp_prob = 0.5 * tmp_prob
        prob = prob + tmp_prob
else:
    prob = (N-K+1.0)/N
    for i in range(1,K):
        tmp = i
        tmp_prob = 1.0/N
        while tmp < K:
            tmp = 2 * tmp
            tmp_prob = 0.5 * tmp_prob
        prob = prob + tmp_prob

print prob

Submission status: Accepted

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

total_prob = 0
for i in range(1, n+1):
    for j in range(0, 10**4):
        if i * 2**j >= k:
            total_prob += 0.5 ** j / n
            break
print(total_prob)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

print(p / n)

Submission status: Accepted

Solution code:
def cnt_operations(i, K):
    ans = 0
    while i < K:
        i *= 2
        ans += 1
    return ans


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

ans = 0
if K <= N:
    ans += (N - K + 1) / N
    for i in range(1, K):
        op = cnt_operations(i, K)
        ans += (1 / N) * (1 / 2)**(op)
else:
    for i in range(1, N + 1):
        op = cnt_operations(i, K)
        ans += (1 / N) * (1 / 2)**(op)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])

nn = [0] * N
ni = N
n = 1
np = 0
while ni >= 1:
    if ni * n >= K:
        nn[ni - 1] = np
        ni -= 1
        continue
    n *= 2
    np += 1

a = 0
for n in nn:
    a += pow(2, nn[0] - n)

a = a / (N * pow(2, nn[0]))

print('{:.10f}'.format(a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

count = 1
while True:
    p += max(0, min(N + 1, math.ceil(K / 2 ** (count - 1))) - math.ceil(K / 2 ** count)) * 0.5 ** count
    count += 1
    if K / 2 ** count < 0.5:
        break

p += max(0, N - K + 1)
print(p / N)

Submission status: Accepted

Solution code:
from sys import stdin
import math
    
def calc(n,k):

    p = 0
    _range = n

    if k == 1:
        return 1

    #dice
    if n >= k:
        p += (n-k+1)/n
        _range = k - 1
    
    for i in range(1, _range + 1):
        x = math.ceil(math.log2(k/i))
        p += 1/n * 0.5 ** x

    return p

def main():
    n,k = [int(x) for x in stdin.readline().rstrip().split()]
    ans = calc(n,k)
    print('{:.11f}'.format(ans))
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

sum=0
for deme in range(1,N+1):
    need_challenge=max(0,math.ceil(math.log2(K)-math.log2(deme)))
    sum+=float((1/N)*((1/2)**need_challenge))
print('{:.13f}'.format(sum))

Submission status: Accepted

Solution code:
#
# abc126 c
#
import math


def main():
    n, k = map(int, input().split())
    ans = 0
    for i in range(1, n+1):
        s = i
        if 1 <= s <= k-1:
            ans += 1/n * (0.5)**math.ceil(math.log2(k/s))
        else:
            ans += 1/n
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

s = 0

a = k
p = 1/2
if a <= n:
  s += p*(n-a+1)

a = (a+1)//2
p = p/2
while True:
  if n >= a:
    s += p*(n-a+1)
  if a == 1:
    break
  p = p/2
  a = (a+1)//2
s += p*n

print(s/n)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N, K = (int(i) for i in input().split())

if K == 1:
    pow_base = 1
else:
    pow_base = math.floor(math.log((K-1),2)) + 1
base = N * (2 ** pow_base)

res = 0
for i in range(1, N+1):
    if i >= K :
        res += (2 ** pow_base)
    else:
        power = math.floor(math.log((K-1) // i, 2)) + 1
        res += 2 ** (pow_base - power)
print(res / base)

Submission status: Accepted

Solution code:
import math

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

p = 0.0

if K>N:
    tp = 0.0
    for i in range(1,N+1):#1~N
        #deme i
        tp += 0.5**math.ceil(math.log2(K/i))
    tp = tp / N
    print(tp)
elif K == 1:
    print(1.0)
else:
    p = (N-K+1.0)/N#No coin
    tp = 0.0
    for i in range(1,K):#1~K-1
        #deme i
        tp += 0.5**math.ceil(math.log2(K/i))
    tp = tp / (K-1.0)
    print(p+(1.0-p)*tp)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
dp = [0]*(k+1)
last = max(n,k)

for i in range(1,last+1):
  if i <= n and i <= k:
    dp[i] += 1 / n
  elif k < i:
    dp[k] += 1 / n
  if i*2 < k:
    dp[i*2] += dp[i] / 2
  elif i < k:
    dp[k] += dp[i] / 2
print(dp[k])

Submission status: Accepted

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

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 = 1
    for j in range(count):
        dec /= 2.0
    result += dec

print(round(result/N, 12))

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
g = 0
if N < K:
    #w = 1/(K-1)
    for i in range(1,N+1):
        t = i
        gk = 1
        while (t < K):
            gk /= 2
            t *= 2
        #print(i,gk,1/gk)
        g += gk
else:
    f = (N-K+1)
    for i in range(1,K):
        t = i
        gk = 1
        while (t < K):
            gk /= 2
            t *= 2
        #print(i,gk,1/gk)
        g += gk
    g += f
print(g/N)

Submission status: Accepted

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

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

total = 0

for i in range(1,n+1):
    memo_05 = 1
    memo_cnt = 0
    a = i
    while(a < k):
        a *= 2
        memo_cnt += 1
    if memo_cnt > 0:
        for j in range(memo_cnt):
            memo_05 *= 0.5

    total += (1/n) * memo_05

print(total)

Submission status: Accepted

Solution code:
import math
N, K= map(int, input().split())
li = []
le = []
for i in range(N):
    A = math.log2(K/(i+1))
    if A < 0:
        kaisu =0
    else:
        kaisu = math.ceil(A)
    le.append(kaisu)
    li.append((0.5**kaisu)/N)
sumli = sum(li)
print(sumli)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
l = input().split()
N = int(l[0])
K = int(l[1])
P = 0
for i in range(1,N+1):
    score = i 
    sub = K - score
    j = 0
    while sub > 0 :    
        score = score * 2
        j += 1
        sub = K - score
    p = 1/N * ((1/2)**j)
    P += p
print(P)

Submission status: Accepted

Solution code:
from decimal import Decimal
from math import log2, ceil
N, K = list(map(int, input().strip().split()))
r = max(N - (K - 1), 0) # 確実に勝てるケース

t = Decimal(0)
d = Decimal(N)
for i in range(1, N-r +1):
    t += 1/d * (Decimal(0.5) ** Decimal(ceil(log2(K/i))))

if r > 0:
    t += Decimal(r) / Decimal(N)

print(str(t)[:14])

Submission status: Accepted

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

if N < K:
    p = 0;
    for i in range(1, N+1):
        p += pow(2, -math.ceil(math.log2(K/i)))/N
else:
    p = 0;
    for i in range(1, K+1):
#        print(i)
        p += pow(2, -math.ceil(math.log2(K/i)))/N
    p = p + (N-K)/N

    
print(p)

Submission status: Accepted

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

P = 0

for i in range(1, N + 1):
    if(i < K):
        count = 1
        while(i * 2 ** count < K):
            count += 1
        #print(count)
        P += 1 / N * (0.5 ** count)
    else:
        P += 1 / N

print(round(P, 12))

Submission status: Accepted

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

from math import ceil

def main():
    n, k = list(map(int, input().split()))
    # ダイスの目iのとき、表が必要な数の配列
    needs = [0] * (n + 1)
    p = 0
    current = len(bin(k)) - 2
    for i in range(1, n + 1):
        if k > i * 2**(current-1):
            needs[i] = current
        else:
            current -= 1
            needs[i] = current
        if needs[i] <= 0:
            p += 1 / n
        else:
            p += 0.5 ** needs[i] / n
    print(p)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

rate = 0
for i in range(1,N+1):
    if i >= K:
        rate += (1/N)
    else:
        count = math.log2((K/i))
        if int(count) == count:
            count = int(count)
        else:
            count = int(count) + 1
        rate += (1/N) * ((1/2)**count)

print(rate)

Submission status: Accepted

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

def getNum(num):
    res = 0
    while True:
        if num >= K:
            break
        res += 1
        num *= 2
    return res

res = 0
for i in range(1, N+1):
    res += (1 / N) * (0.5 ** getNum(i))
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def kakuritsu(dice_me):
    tokuten = dice_me
    kurikaesi = 0
    while tokuten < K:
        tokuten = tokuten * 2
        kurikaesi += 1
    # print('kurikaesi', kurikaesi)
    test_list.append(1 / N * (1 / 2) ** kurikaesi)


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

for i in range(N):
    kakuritsu(i + 1)

print(sum(test_list))

Submission status: Accepted

Solution code:
import math
answer=0

N,K=map(int,input().split())
for i in range(1,N+1):
    p=(1/2)**(math.ceil(math.log(K/i,2)))
    if i>=K:
        p=1
    answer+=(1/N)*p

print(round(answer,13))

Submission status: Accepted

Solution code:
import math
def near_pow(n):
    if n <= 0:
        return 0
    elif (n & (n - 1)) == 0:
        ret = -1
        while n>0:
             ret += 1; n >>= 1
        return ret

    else:
        ret = 0
        while n>0:
             ret += 1; n >>= 1
        return ret
N,K = map(int,input().split())
ans = 0.0

for i in range(1,N+1):
    a = math.ceil(K/i)
    ans += (1/N)*(0.5**near_pow(a))
print(ans)

Submission status: Accepted

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

sigma = 0

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

    while i * (2 ** coin) < K:
        coin += 1

    sigma += ((1 / N) * (0.5 ** coin))

print(sigma)

Submission status: Accepted

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

point = 0
result = 0
for index in range(n):
    if point >= k:
        break
    
    tmp_count=0
    tmp_value=(index+1)
    while tmp_value < k:
        tmp_value*=2
        tmp_count+=1
        
    double_num=tmp_count

    result+=(1/n)*((1/2)**double_num)


print(result)

Submission status: Accepted

Solution code:
import math


def probability(init, K):
    if init >= K:
        return 1
    min_n = math.ceil(math.log(K/init, 2))
    p = 1 / (2 ** min_n)
    return p


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

p = 0
for init in range(1, N+1):
    p += 1/N * probability(init, K)

print(p)

Submission status: Accepted

Solution code:
def judge(j,k):
    if j>=k:
        return(1)
    else:
        d=judge(2*j,k)
        return(1/2*d)
        
n,k= map(int,input().split())
sum=0
for i in range(n):
    sum+=judge(i+1,k)
print(sum/n)

Submission status: Accepted

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

dice_max = N
goal = K



dice = list(range(1, dice_max+1))

import math

ans = 0
    
for d in dice:
    win = 1
    if d < goal:
        lose_num = math.ceil(math.log2(goal / d))
        #print(lose_num)
        win = 1 / (2** lose_num)

        
    ans += win

ans /= len(dice)
print('{:.15g}'.format(ans))

# 0.999973749998

Submission status: Accepted

Solution code:
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/2) ** math.ceil(math.log2(k/i))) / n
print(p)

Submission status: Accepted

Solution code:
import math

def solve():
    N, K = [int(_) for _ in raw_input().split()]
    ret = 0
    coin_prob = 1
    tmp_cnt = 0
    start = N
    if N >= K:
        ret += (N - K + 1) * 1.0 / N
        start = K - 1
    for i in range(start,0,-1):
        cnt = int(math.ceil(math.log(K * 1.0 / i, 2)))
        coin_prob *= (0.5 ** (cnt - tmp_cnt))
        tmp_cnt = cnt
        ret += coin_prob / N
    print str(ret)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def pj(n, k):
  p=n
  ans=1.0
  while(True):
    if (k <= p):
      break
    ans /= 2
    p*= 2
  return ans

n,k=map(int,input().split())
ans=0.0
for i in range(1,n+1):
  ans += (float(1.0)/float(n))*pj(i, k)
print("%.12f"%ans)

Submission status: Accepted

Solution code:
#! usr/bin/env python
# -*- coding: utf-8 -*-

from collections import deque
import heapq
import math
import bisect


def main():
    N, K = map(int, input().split())
    dp = [0] * 200005

    for i in range(K-1, 0, -1):
        if 2 * i >= K:
            dp[i] = 0.5
        else:
            dp[i] = 0.5 * dp[2*i]

    ans = max(0, N-K+1) / N
    for i in range(1, min(N+1, K)):
        ans += dp[i] / N

    print("{:.10f}".format(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ans=max(n-k+1,0)
a,b,c=k,k,1
while a!=1:
  b=(a+1)>>1
  ans+=(min(a,n+1)-min(b,n+1))/(2**c)
  c+=1
  a=b
print(ans/n)

Submission status: Accepted

Solution code:
import math
import numpy as np

def findnext(l, mx):
    for i in range(1, mx+1):
        if i not in l:
            return i
    return -1

def solve():
    n, k = map(int, input().split())
    prob = np.float64(0.0)
    for i in range(1, n+1):
        #i:出目
        #L:必要なコイン投げ回数
        if k > i:
            L = math.ceil(math.log2(float(k)/float(i)))
            prob += np.power(np.float64(0.5), L)
        else:
            prob += np.float64(1.0)

    prob = prob / np.float64(n)
    print(prob.astype(str))

solve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

    ans = 0
    dice = 1
    
    while dice <= N:
        p = 1/N
        score = dice
    
        while score < K:
            score *= 2
            p /= 2

        ans += p
        dice += 1
        
    print ("%.10f" % (ans))
    
if __name__ == "__main__":  
    solve()

Submission status: Accepted

Solution code:
import copy

class Solver:
    def __init__(self, _n, _k):
        self.n = _n
        self.k = _k

        self.solve()
    
    def solve(self):
        ans = 0.0

        for point in range(1, self.n + 1):
            i = 0
            while point < self.k:
                point = point * 2
                i = i + 1
            ans = ans + (1.0 / self.n) * pow((1.0 / 2), i)

        # print("{:.09f}".format(ans))
        print(ans)
def main():
    n, k = (int(i) for i in input().split())
    Solver(n, k)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def check(n):
  cnt = 0
  while n < K:
    n *= 2
    cnt += 1
  return cnt

import decimal

dec = decimal.Decimal

ind = 1
point = 0
x = 1 / N
y = 1 / 2
for i in range(ind, N+1):
  res = check(i)
  point += x * (y**res)
print(point)

Submission status: Accepted

Solution code:


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


tab = [0]*(10**5//2)



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

    tab[count] += 1
    
#    print(x)

acc = 0
for i in range(len(tab)):
    e = tab[i]
    if e == 0:
        continue

#    print((e,i))
    acc += e * (.5**i)

print( acc/n )

Submission status: Accepted

Solution code:
import decimal

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

total_ans=0
#1
for i in range(1,n+1):
  point=i
  num=0
  ans=1/n
  while point<k:
    point=point*2
    ans=ans/2
  total_ans=total_ans+ans

print(total_ans)

Submission status: Accepted

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

ret=0

for i in range(1,n+1):
    p=math.ceil(math.log2(k/i))
    p=p if p>0 else 0
    ret+=math.pow(0.5,p)/n

ret=math.floor(ret*1e12)*1e-12
print(ret)

Submission status: Accepted

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

s = 0.0
for i in range(1,N+1):
	c = 0
	while i*pow(2, c) < K:
		c = c+1
	s = s + 1/N*pow((1/2), c)
	
print(s)

Submission status: Accepted

Solution code:
#C問題
import math
N, K =map(int, input().split())
#確率
p = []
for i in range(1, N+1):
    if i < K:
        #print(i)
        a = math.ceil((math.log2(K/i)))
        #print(a)
        p.append((0.5**a)/N)
        #print(p)
    if i >= K:
        p.append(1/N)
        #print(p)
print(sum(p))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# input
a, b = map(int, input().split())
out = 0
for i in range(1, a+1):
    if i < b:
        t = 0
        o = i
        while o < b:
            o *= 2
            t += 1
            #print(i, o, t)
        out += (1/a)*(0.5**t)
    else:
        out += (1/a)
# output
print(out)

Submission status: Accepted

Solution code:
import math
N, K = [int(_) for _ in input().split()]
p = math.ceil(math.log2(K))
e = []
for i in range(p + 1):
    e += [(i, math.ceil(K / 2**i))]
for i in range(p + 1):
    if N >= e[i][1]:
        e = e[i:]
        e = [(e[0][0], N + 1)] + e
        break
ans = 0
for i in range(1, len(e)):
    ans += (e[i - 1][1] - e[i][1]) * 2**(p - e[i][0])
print(ans / N / 2**p)

Submission status: Accepted

Solution code:
import math
nk = list(map(int,input().split()))
s = 0
for n in range(1,nk[0]+1):
    if n >= nk[1]:
        s += 1/nk[0]
    else:
        s += 0.5**math.ceil(math.log2(nk[1]/float(n)))/nk[0]
print(s)

Submission status: Accepted

Solution code:
import math

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

prod = 0

if K <= N:
    prod = (N-K+1)/N
    case = K
else:
    case = N+1

for i in range(1,case):
    exp = math.ceil(math.log2(K/i))
    prod  = prod + 1/N * 0.5**exp

print(prod)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()




dp = [0]*(k-2)+[1]+[0]
m = 1
while True:
    a = int((k-0.1)//(2**m))
    if a < 1:
        break
    dp[a-1] += 1
    m += 1

b = 0
for i in range(k)[::-1]:
    b += dp[i]
    dp[i] = b

if k == 1:
    dp = [0]

ans = 0
for j in range(n):
    if j < k:
        ans += 1/(2**dp[j])
    else:
        ans += 1

print(ans/n)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] = [int(input_raw[0]), int(input_raw[1])]

    ans = 0.0
    if K == 1:
        print 1
        return
    for x in range(1, N + 1):
        #t = (K)/(2 * (x)) + (1 if (K)%(2 * (x)) == 0 else 0)
        if x >= K:
            ans += float(N - x + 1)/float(N)
            break;
        t = math.ceil(math.log(float(K)/float(x), 2))

        ans += (1.0/(2 ** t))/float(N)

    #ans += float(N - x + 1)/float(N)
    print ("%20.15f" % ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import os, sys, re, math

n,k = [int(s) for s in input().split(' ')]

ret = 0
for i in range(n):
    if i+1 >= k:
        ret += 1
    else:
        a = math.ceil(math.log(k/(i+1), 2))
        ret += (0.5) ** a

print(ret / n)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
# aの桁数
a = len(bin(K))-2
c = 0
# print(a)
# 引いたときにK-1以下である確率
prob1 = min(1,(K-1)/N)
prob2 = 1-prob1

cnt = 0
ans = 0
while (K-1)//(2**cnt) > 0:
    #そこに収まる数(maxがN)
    n = min(N, (K-1)//(2**cnt)) - (K-1)//(2**(cnt+1))
    if n > 0:
       ans += n*1.00/(N*2**(cnt+1))
    #    print(cnt+1,n,ans)
    cnt+=1
    
print(ans+prob2)

Submission status: Accepted

Solution code:
import math

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

p = [0] * n
for dice in range(n):
    p[dice] = 1/n
    point = (dice+1)
    while point < k:
        p[dice] *= 1/2
        point *= 2.0

print(sum(p))

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


# N = int(input())
# A = [int(x) for x in input().split()]
# a, b, c = map(int, input().split())
# name1 = str(input())
# alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}
# b = list(map(lambda x: math.ceil(x/10)*10, a))

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

Submission status: Accepted

Solution code:
import math

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

lst = [1]
K2 = 1
while K2 < K:
    K2 *= 2
    lst.append(K2)

cnt = 0
for i in range(1,N+1):
    now = math.ceil(K/i)
    if now == 1:
            cnt += lst[-1]
    else:
         for j in range(len(lst)-1):
            if lst[j] < now <= lst[j+1]:
                cnt += lst[-1] // lst[j+1]

ans = cnt / (N * lst[-1])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

import math

def main():
    n, k = list(map(int, input().split()))
    cand = []
    tk = k
    tn = n
    while tk > 0.5:
        if int(tk) == tk:
            cand.append(max(0, tn-tk+1))
            tn = min(tn, tk-1)
        else:
            cand.append(max(0, tn-int(tk)))
            tn = min(tn, int(tk))
        tk /= 2
    ans = sum(cand[i] * pow(2, len(cand)-i) for i in range(len(cand)))
    print(ans/(n*pow(2, len(cand))))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
if n >= k:
    ans += (n - k + 1) / n

a = k
for i in range(1, 18):
    b = -(-a // 2)
    if b <= n:
        ans += min(a - b, n + 1 - b) / n * (0.5) ** i
    a = b
print(ans)

Submission status: Accepted

Solution code:
import sys
import math

def solve(n, k):
    ans = 0.
    rate = 1./n
    for i in xrange(n):
        if i + 1 >= k:
            ans += rate
        else:
            ans += rate * 0.5 ** math.ceil(math.log(k/(i+1), 2))

    return ans

if __name__ == '__main__':

    n, k = sys.stdin.readline().strip().split(" ")
    print solve(int(n), float(k))

Submission status: Accepted

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

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

sum = 0
x = 0
for i in range(n,0,-1):
    while i * (2 ** x) < k:
        x += 1
    if (i * (2 ** x) > k * 2) and x >= 1:
        x -= 1
    sum += (1/2)**x / n

print(sum)

Submission status: Accepted

Solution code:
import math

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

ans = 0.0

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

print("{:.10f}".format(ans))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
s=0
for n in range(N):
    score=n+1
    cnt=0
    while score<K:
        score*=2
        cnt+=1
    e=1/N*(1/2)**cnt
    if score >=K:
        s+=e
print(s)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def main():
	n, k = map(int, input().split())

	ans = 0
	tmp = 1/n

	for i in range(1, n+1):
		if i >= k:
			ans += tmp
			continue
		count = 0
		num = i
		while True:
			num *= 2
			count += 1
			if num >= k:
				ans += tmp * pow(0.5, count)
				break

	print(ans)



if __name__ == '__main__':
	import sys
	sys.exit(main())

Submission status: Accepted

Solution code:
import math

N, K = map(int, input().split())
if K <= N:
  p = 1 - (K-1)/N
else:
  p = 0
for i in range(1, min(N+1, K)):
  n = math.ceil(math.log(K/i, 2))
  p += 1/N * (1/2 ** n)
print(p)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
n, k = map(int, raw_input().split())

winrate = 0.0


for i in range(n):
    i = i+1
    j = 0
    while(i < k):
        i *= 2
        j += 1
    winrate = winrate + (0.5) ** j

# 文字列の入力
winrate = winrate/n

# 出力
print winrate

Submission status: Accepted

Solution code:

N,K=map(int,input().split())
k=K
p=[0]*20
p[0]=10**5+1
for i in range(19):
    p[i+1]=k
    k=k/2

ans=0
for i in range(N):
    for j in range(19):
        if i+1<p[j] and i+1>=p[j+1]:
            ans+=(1/N)*((1/2)**(j))
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ans = 0
for n in range(1, N+1):
    if n >= K:
        ans += 1 / N
    else:
        L = 1
        V = n * 2
        while V < K:
            V *= 2
            L += 1
        ans += 0.5 ** L / N
print(ans)

Submission status: Accepted

Solution code:
import math

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

tsum=0

for x in range(1,N+1):
	
	logarithm=max(math.ceil(math.log(K/x,2)),0)
	# print(logarithm)
	tsum+=(1/(N*pow(2,logarithm)))

print(tsum)

Submission status: Accepted

Solution code:
from math import log

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

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

print(sum_num / N)

Submission status: Accepted

Solution code:
import math

n,k = map(int,input().split())
ans = 0
pre_ans = 0
for i in range(1,n+1):
    twoNum = 1
    score = i
    while score < k:
        score *= 2
        twoNum *= 2
    ans += twoNum**-1 / n
print(round(ans,12))

Submission status: Accepted

Solution code:
import math
N,K = map(int,input().split())
ite = []
for n in range(1,N+1):
  num = int(math.ceil(math.log2(K/n)))
  if num > -1:
    ite.append(num)
  else:
    ite.append(0)
ans = []
for i in ite:
  ans.append((1/N)*(0.5)**i)
print(sum(ans))