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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


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

p = 0

# 出た目がNから順に評価
# K<100000 なので、2^16まで
for i in range(N,0,-1):
    if i >= K:
        p += 1/N
    elif K/2 <= i < K:
        p += 1/N/2
    elif K/2**2 <= i < K/2:
        p += 1/N/2**2
    elif K/2**3 <= i < K/2**2:
        p += 1/N/2**3
    elif K/2**4 <= i < K/2**3:
        p += 1/N/2**4
    elif K/2**5 <= i < K/2**4:
        p += 1/N/2**5
    elif K/2**6 <= i < K/2**5:
        p += 1/N/2**6
    elif K/2**7 <= i < K/2**6:
        p += 1/N/2**7
    elif K/2**8 <= i < K/2**7:
        p += 1/N/2**8
    elif K/2**9 <= i < K/2**8:
        p += 1/N/2**9
    elif K/2**10 <= i < K/2**9:
        p += 1/N/2**10
    elif K/2**11 <= i < K/2**10:
        p += 1/N/2**11
    elif K/2**12 <= i < K/2**11:
        p += 1/N/2**12
    elif K/2**13 <= i < K/2**12:
        p += 1/N/2**13
    elif K/2**14 <= i < K/2**13:
        p += 1/N/2**14
    elif K/2**15 <= i < K/2**14:
        p += 1/N/2**15
    elif K/2**16 <= i < K/2**15:
        p += 1/N/2**16
    elif K/2**17 <= i < K/2**16:
        p += 1/N/2**17

print(p)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
import math
def deno(x):
    if x >= K:
        return 1
    else:
        count = math.ceil(math.log(K/x, 2))
        return 1 / (2 ** count)
pro = sum(map(deno, range(1,N+1))) / N
print(pro)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
k = K
twofac = 2
boarder = []
enough = 0
while(k > twofac):
    if k % twofac == 0:
        boarder.append(k // twofac)
    else:
        boarder.append(k // twofac + 1)
    twofac *= 2
boarder.append(1)
boarder.insert(0, K)
each = 1 / N
ans = 0
lenb = len(boarder)
for i in range(lenb-1, 0, -1):
    if boarder[i-1] <= N:
        ans += (boarder[i-1]-boarder[i])*each/(2**i)
    else:
        ans += (N-boarder[i]+1)*each/(2**i)
        enough = 1
        break
if enough == 0:
    ans += (N-K+1)*each
print(str(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
dice = 1/n
n = list(range(1,n+1))

import math
def cal(i):
  return dice * (1/2)**max(0,math.ceil(math.log2(k/i)))

print(sum([cal(i) for i in n]))

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
ans = 0
koe = False
for i in range(N):
    a = i + 1
    if a > K-1:
        koe = True
        break
    flag = True
    count = 0
    while flag:
        a = a * 2 # N
        count = count + 1
        if (a >= K):
            flag = False
    ans += 1/N * (1/2)**count
if koe:
    ans += (N-(K-1))/N
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
	N, K = map(int, input().split())
	dp = [0 for _ in range(K+1)]

	if K > N:
		for i in range(1, N+1):
			dp[i] = 1
	else:
		for i in range(1, K):
			dp[i] = 1
		dp[K] += (N-K+1)
	ans = dp[K]
	for i in range(1, min(N+1, K)):
		cur = i
		this_p = dp[i]
		while cur < K:
			this_p *= 0.5
			cur *= 2
		ans += this_p
	print(ans/N)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

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

for i in range(1,min(k,n+1)):
    if math.log(k/i,2)-int(math.log(k/i,2))== 0:
        p = int(math.log(k/i,2))
    else:
        p = int(math.log(k/i,2))+1
    ans +=(1/n)*(0.5**p)
print(ans)

Submission status: Accepted

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

def afterdiceprob(x):
    flag = True
    y = 0
    while(flag):
        if x*2**y >= K:
            break
        y += 1
    return y

sum = 0
kmax = 0
for k in range(1,N+1):
    sum += (1/N)*(1/2)**afterdiceprob(k)
print(sum)

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:
        ee=math.ceil(math.log2(k)-math.log2(i))
        ans+=(1/2)**ee/n
    else:
        ans+=1.0/n
print(ans)

Submission status: Accepted

Solution code:
import math
from decimal import Decimal
N, K = [int(item) for item in input().split()]
b = 0
for i in range(1, N+1):
  tmp = i
  cnt = 0
  while tmp < K:
    tmp *= 2
    cnt += 1
  if i == 1:
    a = (N * 2 ** cnt)
  b += (a / (N * 2 ** cnt))
print(Decimal(b/ a))

Submission status: Accepted

Solution code:
nk = list(map(lambda x: int(x), input().split()))
n = nk[0]
k = nk[1]

poss_points = [i+1 for i in range(n)]
needed_wins = [-1 for i in range(n)]

def convert(x):
  if (x == -1):
    return 0
  else:
    return x

def calc(x):
  return (1/n) * 0.5 ** x

for i in range(n):
  times = 0
  point = poss_points[i]
  if (needed_wins[i] != -1):
    continue

  while(True):
    if (point >= k):
      break
    point = point * 2
    times += 1

  if (times == 0):
    break
    
  next_int = i + 1
  while(times > 0 and next_int <= n):
    needed_wins[next_int-1] = times
    next_int = next_int * 2
    times -= 1

# -1 は0に変換
needed_wins = list(map(convert, needed_wins))

array = list(map(calc, needed_wins))
answer = sum(array)

print(answer)

Submission status: Accepted

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

print(p)

Submission status: Accepted

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

n, k = (int(i) for i in input().split())
#print(a,b)

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

Submission status: Accepted

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

for i in range(N):
    coin_num = math.log(K/(i+1)) / math.log(2)
    if K > (i+1) :
        if int(coin_num) == coin_num:
            pass
        else:
            coin_num = int(coin_num) + 1
        possibility += (1/N) * ((1/2) ** int(coin_num))
    else:
        possibility += (1/N)

print(possibility)

Submission status: Accepted

Solution code:
import numpy as np
N,K = map(int,input().split())
ans = np.full(N,1/N)
ans_2 = np.array(range(N))
ans_2 += 1
prob = 0
for i in range(N):
	if ans_2[N-i-1] >= K:
		prob += ans[N-i-1]
	else:
		while ans_2[N-i-1] < K:
			ans_2 *= 2
			ans *= 1/2
		prob += ans[N-i-1]
print(prob)

Submission status: Accepted

Solution code:
import math
N, K = map(int, input().split())
results = []
for i in range(N+1)[1:]:
  s = -(-K // i)
  r = math.ceil(math.log2(s))
  results.append(1.0/float(N*(2**r)))
print(sum(results))

Submission status: Accepted

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

Submission status: Accepted

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

win_prob = 0

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

Submission status: Accepted

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

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

Submission status: Accepted

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

def twice(now, cnt):
    #print(now)
    if now >= k:
        return cnt
    cnt += 1
    return twice(now * 2, cnt)

if __name__ == '__main__':
    ans = 0
    for i in range(1, n+1):
        cnt = 0
        #print(twice(i, cnt))
        #print((1/2)**int(twice(i)))
        #print(float(1/n))
        ans += float(1/n) * float((1/2)**int(twice(i, cnt)))
    print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
seq = [-1]*N
pos=N
kei = 1
count = 0
result = 0
for i in reversed(range(N)):
    while K>(i+1)*kei:
        kei*=2
        count+=1
    result += 1/kei
print(result/N)

Submission status: Accepted

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

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

print(p)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
pow = [0 for _ in range(n)]
l, r = n-1, 0
while l >= 0:
    while (l+1) * 2**r < k:
        r += 1
    pow[l] = r
    l -= 1
ans = 0
for i in range(n):
    ans += 1/n * 0.5**pow[i]
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
t = 1/N
a = []
X = K
i = 0
for i in range(20):
  if X%2 == 0:
    for j in range(int(X/2)):
      a.append(0.5**(i+1))
    X = X/2
    i += 1
  else:
    for j in range(int((X-1)/2)):
      a.append(0.5**(i+1))
    X = (X+1)/2
    i += 1
if K>N:
  ans = sum(a[K-N-1:])*t
elif K == N:
  ans = (sum(a)+1)*t
else:
  ans = (sum(a)+(N-K+1))*t
print(ans)

Submission status: Accepted

Solution code:
from fractions import Fraction
x, y = list(map(int, input().split(' ')))

ls = []
for start in range(1, x + 1):
    if start < y:
        tmp = start
        turns = 0
        while tmp < y:
            tmp *= 2
            turns += 1

        f1 = Fraction(1, pow(2, turns))        
        ls.append(f1)

t = Fraction(0, 1)
for num in ls:
    t += num

t += Fraction(max(x - y + 1, 0), 1)

print(float(t) / x)

Submission status: Accepted

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

ans = 0

for i in range(1,n+1):
    #print(i)
    if i == k:
        ans += n-k+1
        break
    for j in range(1,200000):
        if i * (2**j) >= k:
            ans += (1/2)**j
            #print(ans)
            break

ans = ans * 1.0/n

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import decimal
input = sys.stdin.readline
decimal.getcontext().prec = 13
dec = decimal.Decimal

s = input().split(" ")
d = int(s[0])
k = int(s[1])

sums = 0
for i in range(d):
    x = i + 1
    j = 0
    while x < k: 
        x = x * 2
        j = j+1
    sums = sums + dec(1)/dec(d) * (dec(1) /dec(2) ** dec(j))

print(sums)
#0.145833333333

Submission status: Accepted

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

def count(i,K):
    sum = 0
    cnt = 0
    while sum < K:
        if cnt == 0:
            sum = i*2
            cnt += 1
        else:
            sum = sum*2
            cnt += 1
    return cnt

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

for i in range(1,N+1):
    if i <= K-1:
        prob += (1/N)*((1/2)**count(i,K))
    else:
        break

print(prob)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

ans = 0

for i in range(1,N+1):
    a = math.ceil(math.log2(K/i))
    ans += 1/(N*(2**a))
    if i >= K:
        ans += (N-K)/N
        break

print(ans)

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 
    times = K / score
    j = 0
    while times > 1 :    
        times = times / 2
        j += 1
    p = 1/N * ((1/2)**j)
    P += p
print(P)

Submission status: Accepted

Solution code:
#ABC126C-DiceAndCoin.py

from sys import stdin
import random

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

result = 0

for n in range(N):
    n = n + 1
    x = 0
    while True:
        if 2 ** x * n >= K:
            break
        x += 1
    result += 1/N * 0.5 ** x

print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

N, K = map(int, input().split())
ans = 0
for m in range(1, N+1):
    x = math.log2(K / m)
    if x - int(x) > 0:
        x += 1
    if x > 1:
        ans += (1/2) ** int(x) / N
    else:
        ans += 1 / N
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import numpy as np

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

x = np.arange(N) + 1
c = np.ceil(np.log2(K / x)).astype(int)
c = c[np.where(c > 0)]
if len(c) == 0:
    print(1)
else:
    cumprod = np.cumprod([0.5] * int(c[0]+1))
    print(2 * np.sum(cumprod[c]) / N + (N - len(c)) / N)

Submission status: Accepted

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

prob=0
for i in range(1,N+1):
    if i>=K:
        prob+=(N-K+1)/N
        break
    power=0
    for j in range(20):
        if i*(2**j)>=K:
            power=j
            break
    prob+=(1/N)*(1/2)**power

print(prob)

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split()]
sum = 0
float(sum)
for i in range(1, N + 1):
    b = i
    con = 0
    while K > b:
        b = b * 2
        con += 1
    else:
        sum += 1 / N * (0.5 ** con)

print(sum)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,k=map(int,input().split(" "))
ans1=0
for i in range(1,n+1):
    c=0
    while(i<k):
        i*=2
        c+=1
    ans1+=0.5**c
   # print(c)
print(ans1*(1/n))

Submission status: Accepted

Solution code:
import math

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

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

print(sum / n)

Submission status: Accepted

Solution code:

if __name__ == '__main__':
    n,k = list(map(int, input().split()))
    n2 = n
    count = 1
    kakuritu = 0

    while(n2 != 0):

        ktop = int(n2 - k + 1)
        if(ktop > 0):
            kakuritu += ktop / n * 1 / count
            n2 -= ktop

        k /= 2
        count *= 2
        
    print(kakuritu)

Submission status: Accepted

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

from fractions import Fraction

probability = Fraction(1, N)
probability_total = 0

for i in range(N):
    count = 0
    point = i + 1
    while K > point:
        count += 1
        point = point * 2
    probability_total = probability_total + probability * Fraction(1, 2) ** count

print(float(probability_total))

Submission status: Accepted

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

ans = 0
for i in range(1, N+1):
    c = 0
    t = i
    while t < K:
        t *= 2
        c += 1

    ans += 1/float(N) * 0.5**c
print(ans)

Submission status: Accepted

Solution code:
men, kazu = map(int,  input().split())

ans = 0

for i in range(men):
    ansKazu = i + 1
    kaisuu = 0
    while ansKazu < kazu:
        ansKazu = ansKazu * 2
        kaisuu = kaisuu + 1

    prob = 1/men * ((1/2) ** kaisuu)
    ans = ans + prob

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

p = 0
for i in range(n):
  if (i+1 < k):
    tp = math.ceil(math.log2(k/(i+1)))
    p = p + 1 / (2 ** tp)
  else:
    p = p + 1

p = p / n
print(p)

Submission status: Accepted

Solution code:
import math

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

p = 0
N_inv = 1.0/N

for ii in range(1,N+1):
    if K > ii:
        #print('exp')
        exp_n = math.ceil(math.log(K/ii,2))
        p = p + N_inv * (0.5)**exp_n
        #print(ii,exp_n,p)
    else:
        p = p + N_inv
        #print(ii,N_inv2,p)

print(p)

Submission status: Accepted

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

nij = []

for i in range(K):
    if 2 ** (i+1) >= K * 4:
        break
    nij.append(2 ** i )
    
ans = 0
cur = len(nij)-1

for i in range(N):
    for j in range(len(nij)):
        #print(i,j,nij[cur-j])
        if nij[cur-j]*(i+1) >= K and nij[cur-j-1]*(i+1) < K:
            #print(cur-j,nij[cur-j],0.5 ** (cur-j+1) )
            ans = ans + 1 / N * 0.5 ** (cur-j)
            #print(i+1)
            break
            #print(1 / N * 0.5 ** (cur-j))
        elif (i+1) >= K:
            ans = ans + 1 / N
            #print(i+1)
            break

print(ans)

Submission status: Accepted

Solution code:

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

def countZero(f):
    if f >= 0:
        return -1
    s = '{:.11f}'.format(f)
    if s.find('.') < 0:
        return -1

    n = s.split('.')[1]
    ss = str(n)
    count = 0
    for i in range(len(ss)):
        if ss[i] == '0':
            count +=1
        else:
            break
    return count
    
prob = 0
for i in range(N):
    n = N - i
    n2 = n
    count = 0
    while True:
        if n2 >=K:
            break
        count+=1
        n2 = n2*2
#     print(n, n2, count, (1/N) * pow(0.5, count))
    ans = (1/N) * pow(0.5, count)
    if countZero(ans) >= 11:
        break
    else:
        prob += ans

print(prob)

Submission status: Accepted

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

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

    p = [1 / N] * N

    for i in range(1, N+1):
        count = 2
        point = i
        while point < K:
            p[i-1] *= 0.5
            point = point * count
        # print(point, p[i-1])
    print(sum(p))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import math

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

if K<=N:
    for i in range(K-1):
        m = math.ceil(np.log2(K/(i+1)))
        P += float(0.5**m)
    print(float((N-K+1+P)/N))
else:
    for i in range(N):
        m = math.ceil(np.log2(K/(i+1)))
        P += float(0.5**m)
    print(float(P/N))

Submission status: Accepted

Solution code:
# def gcd(a_gcd, b_gcd):
#     while b_gcd != 0:
#         a_gcd, b_gcd = b_gcd, a_gcd % b_gcd
#     return a_gcd
#
#
# def lcm(a_lcm, b_lcm):
#     return a_lcm * b // gcd(a_lcm, b_lcm)
#
#
# def max_sum(N_max_sum, a_max_sum):
#     dp = [0] * (N_max_sum + 1)
#     for i in range(N_max_sum):
#         dp[i + 1] = max(dp[i], dp[i] + a_max_sum[i])
#     return dp[N]
#
#
# def knapsack(N_knapsack, W, weight, value):
#     inf = float("inf")
#     dp = [[-inf for _ in range(W+1)] for j in range(N_knapsack + 1)]
#     for i in range(W+1):
#         dp[0][i] = 0
#
#     for i in range(N_knapsack):
#         for w in range(W+1):
#             if weight[i] <= w:
#                 dp[i+1][w] = max(dp[i][w-weight[i]]+value[i], dp[i][w])
#             else:
#                 dp[i+1][w] = dp[i][w]
#     return dp[N_knapsack][W]


import math

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

sum = [0 for _ in range(math.ceil(math.log(K, 2)) + 1)]


for i in range(N, 0, -1):
    for j in range(len(sum)):
        if K <= i * pow(2, j):
            sum[j] += 1
            break

ans = 0

for i in range(len(sum)):
    # print(pow(2, i))
    # print(sum[i])
    ans += sum[i] / (pow(2, i) * N)

print(ans)

Submission status: Accepted

Solution code:
import math

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

pprob = 0
for n in range(1, N+1):
    if K/n < 1:
        throw = 0
    else:
        throw = math.ceil(math.log2(K/n))
    pprob += ((1 / 2) ** throw) / N

print(pprob)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import decimal

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

p = 1
times = 0
ans = 0

while N * 2 ** times < K:
    times += 1
p = 0.5 ** times

for i in range(N, 0, -1):
    if i * 2 ** times < K:
        times += 1
        p /= 2
    ans += p

print(decimal.Decimal(ans / N))

Submission status: Accepted

Solution code:
from decimal import *
N,K = map(int, raw_input().split())
ans = Decimal(0)
if N >= K:
	ans += Decimal(N-K+1)/Decimal(N)
pre = min(N+1,K)
sisu = 1
while True:
	if(pre == 1):
		break
	now = K - (K * (2**sisu - 1))/ (2**sisu)
	if(pre > now):
		ans += Decimal(pre-now)/Decimal(N * 2**sisu)
	sisu += 1
	pre = min(now,N+1)
print(ans)

Submission status: Accepted

Solution code:
import math

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

prob = 0

def calc_count(score,k):
    ''' 出た目とKから達成するための振る回数を割り出す '''
    count = 0
    while ( score < k ) :
        count = count + 1
        score = score * 2
    return count

def calc_prob(n, count):
    return 1/n * (0.5**count)


for i in range(1,n+1):
    prob = prob + calc_prob(n, calc_count(i, k))

print(prob)

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
box = []
ans = 0
for i in range(20):
    if 2**i >= k:
        aa = i
        break
for j in range(1,n+1):
    cnt = 0
    for h in range(20):
        #print(aa)
        #print(j/(2**h))
        if (j/(2**h))*2**aa >= k:
            cnt = h
            #print(cnt)
        else:
            break
    box.append(cnt)
for y in range(1,n+1):
    ans += (1/n)*((1/2)**(max(0,(aa-box[y-1]))))
    #print((1/n)*((1/2)**(aa-box[y-1])))
    #print((1/n)*((1/2)**(aa-box[y-1]))
    #print((1/2)**(max((aa-box[y-1]),0))
#print(aa)
#print(box)
print(ans)

Submission status: Accepted

Solution code:
import math

s,need = list(map(int, input().split())) 

pos=0.0

if(s>=need):
    pos+=(0.0+s-need)/s

now=min(s,need)
while(True):
    p=math.ceil(math.log2(float(need)/now))
    pos += 1.0/s * 0.5**p
    if(now==1):
        break
    now-=1
        
print(pos)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# IMPORT ###############################################################################################################
import sys                                                      # システム
sys.setrecursionlimit(10**6)                                    # 再帰処理の上限変更
from collections import deque, Counter                          # キュー・個数カウント
from itertools   import accumulate, permutations, combinations  # 累積和・順列・組み合わせ
from operator    import itemgetter                              # ソート補助
from bisect      import bisect_left, bisect_right, bisect       # 二分探索
from heapq       import heappop, heappush                       # プライオリティキュー
from fractions   import gcd                                     # 最大公約数
from math        import ceil, floor, sqrt, cos, sin, tan, pi    # 数学処理
from copy        import deepcopy                                # オブジェクトコピー
import numpy         as np                                      # 数値計算

# MAIN #################################################################################################################
def main():
    # Init #############################################################################################################
    im = InputManager()
    # Input ############################################################################################################
    n, k = im.inputMultiple()
    # Logic ############################################################################################################
    ans = 0
    powers = [(2 ** i) for i in range(18)]
    possibilities = [(0.5 ** i) for i in range(18)]
    for i in range(n):
        score = i + 1
        for power, possibility in zip(powers, possibilities):
            if ((score * power) >= k):
                ans = ans + possibility
                break
    ans = ans / n
    # Output ###########################################################################################################
    print("{:.10f}".format(ans))
    # Return ###########################################################################################################
    return

# INPUT MANAGER ########################################################################################################
class InputManager(object):
    def __init__(self):
        pass

    @staticmethod
    def inputSingle(dtype=int):
        return dtype(input())
    
    @staticmethod
    def inputMultiple(dtype=int, aslist=False):
        if aslist:
            return list(map(dtype, input().split()))
        else:
            return map(dtype, input().split())

    @staticmethod
    def input2D(h, dtype=int):
        return [list(map(dtype, input().split())) for i in range(h)]

# CALL MAIN ############################################################################################################
main()

Submission status: Accepted

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

rate = 0
for i in range(1, N+1):
    if i >= K:
        rate += 1/N
        continue
    div = 1
    while i*(2**div) < K:
        div += 1
    rate += 1/N * (1/2)**div

print(rate)

Submission status: Accepted

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

print(Sum/N)

Submission status: Accepted

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

a,b = map(int,input().split())
pub = 0.0

for i in range(a):
    k = i + 1
    s = 1.0/ a
    while k <= b -1:
        k = k * 2
        s = s * 0.5
    pub += s

print('{:.12g}'.format(pub))

Submission status: Accepted

Solution code:
def aaa(num, target):
    a = 0
    aaa = num
    while target > aaa:
        a += 1
        aaa = aaa * 2
    return a


if __name__ == "__main__":
    N, K = map(int, input().split())

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

    print(ans)

Submission status: Accepted

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

def renzoku(K,A):
    s=0
    while K>A:
        A*=2
        s+=1
    return s
        
out=0

for i in range(1,N+1):
    out+=(N*2**renzoku(K,i))**(-1)

print(out)

Submission status: Accepted

Solution code:
n, k = map( int, input().split() )
p_n = 0
s = 0
m = k
while m > 1 :
    m = m / 2
    s += 1
geta = 2 ** s
p_n += 1
for i in range(1, n) :
    s = 0
    m = k / (i+1)
    while m > 1 :
        m = m / 2
        s += 1
    p_n += geta / 2 ** s
print(p_n / n/ geta)

Submission status: Accepted

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

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

print (sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,k=map(float,input().split(" "))
ans1=0
ans=0
n=int(n)
for i in range(1,n+1):
    c=0
    ans1=0
    while(i<k):
        i*=2
        c+=1
    ans1+=2**c
    ans+=1/ans1
   # print(c)
print(ans*(1/n))

Submission status: Accepted

Solution code:
n,k=input().split()
n=int(n)
k=int(k)
i=0
ii=0
ans=0.0
while i!=n:
    i=i+1
    j=i
    ii=0
    anss=1
    while j<k:
       j=j*2
       ii=ii+1
       anss=anss*1/2

    ans=ans+anss
ans=ans/n
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n,k=map(int,input().split(" "))
if k<=n:#最初にk以上を出す確率
  p=n-k+1
else:
  p=0
#0を1度も引かない場合勝てる。
for i in range(min(n,k-1)):#0~k-2
  x=math.ceil(math.log2(k/(i+1)))#割り切れてしまった場合1多くカウントすることになる
  p+=(0.5)**x
print(p/n)

Submission status: Accepted

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

l = [1,]
a = 1
ans = 0
while a <= 100000:
    a *= 2
    l.append(a)

# print(l)
for i in range(1,n+1):
    tmp = k/i
    if tmp <= 1:
        ans += (n-i+1)/n
        break
    for j in l:
        if j >= tmp:
#            print(j,1/j)
            ans += 1/j/n
            break

# ans /= n
print(ans)

Submission status: Accepted

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

ans=0
b=0

def ho(a,K):
    for za in range(0,10000):
        if a*2**za>=K:
            break
    return za

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

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
ans = 0
from math import ceil,log2

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

ans = ans/N
print(ans)

Submission status: Accepted

Solution code:
def celling(A, B):
    return (A + B - 1) // B

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

ans = 0
flipnum = 0
facepossibility = 1

targetMax = N
targetMin = K
if K > 1:
    while targetMax > 0:
        targetMin = celling(K, 2**flipnum)
        if targetMin > targetMax:
            flipnum += 1
            continue
        ans += (targetMax - targetMin + 1) / (N * 2 ** flipnum)
        targetMax = targetMin - 1
        flipnum += 1
    print(ans)
else:
    print("1")