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 python3
import sys

def calc(n, k):
    ret = 0
    while n < k:
        n *= 2
        ret += 1
    return ret


def solve(N: int, K: int):
    ret = 0.0
    for i in range(1, N + 1):
        ret += (0.5 ** calc(i, K)) * (1.0 / N)
    print(ret)
    return


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:
import sys
import math
sys.setrecursionlimit(10**6)
from collections import defaultdict

n,k=map(int,input().split())
ans=0
for i in range(1,n+1):
    if i>=k:
        ans+=1/n
    else:
        ans+=1/(n*2**int(1-1/(10**9)+math.log((k/i),2)))
#print(i,2**int(math.log((k/i),2)),ans)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ans = 0
for x in range(1, N+1):
    r = 1.
    while x < K:
        r /= 2.
        x <<= 1
    ans += r
print("%.16f" % (ans / N))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)
#input = sys.stdin.readline
n,k = map(int,input().split())
ans = 0
for i in range(1,n+1):
    a = i + 0
    b = 1
    while a < k:
        b /= 2
        a*=2
    ans += (1/n)*b
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

	for i in range(1, n + 1):
		x = 0
		while i < k:
			i <<= 1
			x += 1
		ans += (1 / n) / (1 << x)

	print(ans)

	return 0

main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
X=[0 for i in range(N)]
for i in range(1,N+1):
    j=i
    tmp=1
    while(j<K):
        j*=2
        tmp/=2
    X[i-1]=tmp
print(sum(X)/N)

Submission status: Accepted

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

Submission status: Accepted

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

print(ans/n)

Submission status: Accepted

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

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

Submission status: Runtime Error

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

ans = 0

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

ans/=n

print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int n,k;

int main(){
  cin >> n >> k;
  
  double res = 0;
  
  for(int i = 1; i <= n; ++i){
    //cout << i << " " << res << endl;
    if(i >= k){
      double cou = 1.0 / n;
      res += cou;
    }else{
      double  cou = 1;
      int c = i;
      while(c < k){
        cou /= 2;
        c *= 2;
      }
      res += cou / n;
    }
  }
  
  cout << res << endl;
}

Submission status: Runtime Error

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

ans = 0
for i in range(1, K):
    if i > N:
        break
    x = np.ceil(np.log2(K/i))
    p = (1/2)**x
    ans += p

ans *= 1/N

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

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

Submission status: Runtime Error

Solution code:
D = int(input())
P = int(input())
ans = 0.0
def func(i):
    t = 0
    while(i < P):
        i *= 2
        t += 1
    return t

for i in range(1, D + 1):
    ans += float((1/D)) * float(((1 / 2) ** func(i)))

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
K = int(input())
result = 0
for i in range(1,N+1):
    prob = 1
    count = i 
    while count < K:
        prob *= 0.5
        count *= 2
    result += prob /N
print(result)

Submission status: Runtime Error

Solution code:
import math

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

# for small
score = 0
times = []
for i in range(1, min(n + 1, k)):
    times.append(math.ceil(math.log2((k / i))))
bottom_max = times[0]
for t in times:
    score += 2 ** (bottom_max - t)
score /= 2 ** (bottom_max) * n

# for big
big = [i for i in range(k, max(k, n + 1))]
score += len(big) / n
print('{:.10f}'.format(score))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math
n, k = map(int, input().split())
ans = 0.0
if n >= k:
  ans += (n-k+1)/n
  
for i in range(1, min(n+1, k)):
  ans+= (1/2)**(floor(math.log2(k/i))+1)
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
p = 0
for i in range(1, n + 1):
    if i < k:
        count = 1
        while i * count < k:
            count += 1
        p += 0.5 ^ float(count)
    else:
        p += 1
print(p/n)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
p = 0
for i in range(1, n + 1):
    if i < k:
        count = 1
        while i * count < k:
            count += 1
        p += 0.5 ^ count
    else:
        p += 1
print(p/n)

Submission status: Runtime Error

Solution code:
def f(n):
    cnt = 0
    while n != 0:
        n //= 2
        cnt += 1
    return cnt

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

cnt = f(k)
ans = 0
num = n
for i in range(n):
    if k // (i+1) < 2**(cnt - 1):
        cnt -= 1
    ans += (1 / num)*(0.5 ** cnt)
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
e=[0]*(k)
e[-2]=1
now=k
while now!=1:
  if now%2==0 and now!=2:
    now=now//2
    e[now-2]+=1
  elif now==2:
    now+=-1
    e[now-1]+=1
  else:
    now=now//2
    e[now-1]+=1
e_=[]
for i in range(k):
  if i==0:
    e_.append(e[k-1-i])
  else:
    e_.append(e[k-1-i]+e_[-1])   
ans=0    
if n<k:
  for i in range(n):
    ans+=((1/2)**e_[k-1-i])*(1/n)
  print(ans)  
else:
  for i in range(k):
    ans+=((1/2)**e_[k-1-i])*(1/n)
  ans+=(1/n)*(n-k)
  print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
e=[0]*(k)
e[-2]=1
now=k
while now!=1:
  if now%2==0 and now!=2:
    now=now//2
    e[now-2]+=1
  elif now==2:
    now+=-1
    e[now-1]+=1
  else:
    now=now//2
    e[now-1]+=1
e_=[]
for i in range(k):
  if i==0:
    e_.append(e[k-1-i])
  else:
    e_.append(e[k-1-i]+e_[-1])   
ans=0    
if n<k:
  for i in range(n):
    ans+=((1/2)**e_[k-1-i])*(1/n)
  print(ans)  
else:
  for i in range(k):
    ans+=((1/2)**e_[k-1-i])*(1/n)
  ans+=(1/n)*(n-k)
  print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

expo = (math.ceil(math.log(K,2)))

ans = 0
bunbo = 1/N
for i in range(N):
    ans = ans + (bunbo * (1/2)**expo)
    expo = expo - 1

print(ans)

Submission status: Runtime Error

Solution code:
 n,k=(int(x) for x in input().split())
 total=0
 j=0
 count=0
 while k>(2**j):
     j=j+1
 for i in range(j,1,-1):
     pro=(1/n)*((1/2)**i)
     total=total+pro
     count=count+1
 while(count<n-1):
     total=total+1/n
     count=count+1
 print(round(total,12))

Submission status: Runtime Error

Solution code:
import numpy as np
import math

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

ans = 0
for n in range(1,N+1):
    p = np.log2(K/n)
    p = math.ceil(p)
    
    if p < 0:
        p=0
    
    ans_temp = (1/N)*(1/2)**p
    ans+=ans_temp
    
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
for i in range(21):
  if k<=2**i:
    t=i
    break
   
#print(t)
if n>=k:
  ans=1/n*((1/2**t)*(2**(k-1)-1)+n-k+1)
else:
  ans=1/n*(1/2**t)*(2**(n)-1)
print('{:.13f}'.format(ans))

Submission status: Runtime Error

Solution code:
import decimal
n,k=map(int,input().split())
num=[]
num2=[]
num4=0
num5=n
if n>=k:
    num4=decimal.Decimal((n-k+1)/n)
    n=k-1
num6=-1*(k//(-1*n))
for i in range(18):
    num.append(2**i)
for i in range(18):
    if num6<=num[i+1]:
        num6=i
        break
for i in range(18):
    if num[i]>=n:
        num2.append(n-num[i-1])
        break
    else:
        if i==0:
            num2.append(1)
        else:
            num2.append(num[i]-num[i-1])
ans=0
num3=len(num2)
for i in range(len(num2)):
    ans+=num2[i]*(2**(i))
print((decimal.Decimal(decimal.Decimal(ans/num5)/(2**(num3+num6))))+num4)

Submission status: Runtime Error

Solution code:
import decimal
n,k=map(int,input().split())
num=[]
num2=[]
num4=0
num5=n
if n>=k:
    num4=decimal.Decimal((n-k+1)/n)
    n=k-1
num6=-1*(k//(-1*n))
for i in range(18):
    num.append(2**i)
for i in range(17):
    if num6<=num[i+1]:
        num6=i
        break
for i in range(17):
    if num[i]>=n:
        num2.append(n-num[i-1])
        break
    else:
        if i==0:
            num2.append(1)
        else:
            num2.append(num[i]-num[i-1])
ans=0
num3=len(num2)
for i in range(len(num2)):
    ans+=num2[i]*(2**(i))
print((decimal.Decimal(decimal.Decimal(ans/num5)/(2**(num3+num6))))+num4)

Submission status: Runtime Error

Solution code:
from math import ceil, log2, pow

def mi():
    return map(int, input().split())

def main():
    N, K = mi()
    ans = 0
    for i in range(1, N+1):
        ans += pow(0.5, max(0, ceil(log2(K)-log2(i))))/N
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
N,K=map(int,input().split())
pro=0
if N==1 and K==1:
    print(1)
elif N>=K:
    pro+=(N-K+1)/N
    for k in range(1, K):
        r = math.ceil(math.log2(K / k))
        pro += 0.5**r / N
    print(pro)

else:
    for k in range(1, N+1):
        r = math.ceil(math.log2(K / k))
        pro += 0.5**r / N
    print(pro)

Submission status: Runtime Error

Solution code:
import math
N,K=map(int,input().split())
pro=0
if N==1 and K==1:
    print(1)
elif N>K:
    pro+=(N-K)/N
    for k in range(1, K):
        r = math.ceil(math.log2(K / k))
        pro += 0.5**r / N
    print(pro)

else:
    for k in range(1, N+1):
        r = math.ceil(math.log2(K / k))
        pro += 0.5**r / N
    print(pro)

Submission status: Runtime Error

Solution code:
import math
N,K=map(int,input().split())
pro=0
if N==1 and K==1:
    print(1)
elif N>=K:
    pro+=(N-K)/N
    for k in range(1, K):
        r = math.ceil(math.log2(K / k))
        pro += 0.5**r / N
    print(pro)

else:
    for k in range(1, N+1):
        r = math.ceil(math.log2(K / k))
        pro += 0.5**r / N
    print(pro)

Submission status: Runtime Error

Solution code:
import math
N,K=map(int,input().split())
pro=0
if N==1 and K==1:
    print(1)
elif N>=K:
    pro+=(N-K)/N
    for k in range(1, K):
        r = math.ceil(math.log2(K / k))
        pro += 0.5**r / N
        print(pro)

else:
    for k in range(1, N+1):
        r = math.ceil(math.log2(K / k))
        pro += 0.5**r / N
        print(pro)

Submission status: Runtime Error

Solution code:
import math
N,K=map(int,input().split())
pro=0
if N==1 and K==1:
    print(1)
elif N>=K:
    pro+=(N-K)/N
    for k in range(1, K):
        r = math.ceil(math.log2(K / k))
        pro += 0.5**r / N
else:
    for k in range(1, N+1):
        r = math.ceil(math.log2(K / k))
        pro += 0.5**r / N
print(pro)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math

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

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

print(ans)

Submission status: Runtime Error

Solution code:
import decimal
import math

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

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

print(ans)

Submission status: Runtime Error

Solution code:
import decimal
import math

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

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

print(ans)

Submission status: Runtime Error

Solution code:
import decimal
import math

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

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

print(ans)

Submission status: Runtime Error

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

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

print(ans)

Submission status: Runtime Error

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

l=[]
point=k
l.append(k)
while point>1:
    if point%2==0:
        point=point//2
    else:
        point=(point//2) +1
    l.append(point)

m=len(l)

if n>=k:
    ans1=0
    for i in range(m-1):
        count=l[i]-l[i+1]
        prob=0.5**(i+1)
        ans1+=prob*count
    ans=ans1+(n-k+1)
else:
    ans2=0
    for i in range(m-1):
        if n>=l[i]:
            b=i
            break
        else:
            continue
        break
    ans2+=((0.5)**b)*(n-l[b]+1)
    for i in range(b,m-1):
        count=l[i]-l[i+1]
        prob=0.5**(i+1)
        ans2+=prob*count
    ans=ans2



print(ans/n)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
w = max((n-k+1) / n, 0)
coin_win = 0
for i in range(1, min(k, n+1)):
    for x in range(1, 18):
        if i * (2 ** x) >= k:
            coin_win += 1 / (2 ** x)
            break
print(w + (1-w) * coin_win / min(k-1, n))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
w = max((n-k+1) / n, 0)
coin_win = 0
for i in range(1, min(k, n+1)):
    for x in range(1, 18):
        if i * (2 ** x) >= k:
            print(x)
            coin_win += 1 / (2 ** x)
            break
print(w + (1-w) * coin_win / min(k-1, n))

Submission status: Runtime Error

Solution code:
n,k = map(int, input())
lis = []
for i in range(1, n+1):
    count = 0
    while i < k:
        i *= 2
        count += 1
    lis.append(count)
result = 0
for i in lis:
    result += 1 / n * 0.5 ** i
print(result)

Submission status: Runtime Error

Solution code:
n,k = map(int, input())
lis = []
for i in range(1,n+1):
    count = 0
    while i < k:
        i *= 2
        count += 1
    lis.append(count)
result = 0
for i in lis:
    result += 1 / n * 0.5 **i
print(result)

Submission status: Runtime Error

Solution code:
n,k = map(int, input())
lis = []
for i in range(1,N+1):
    count = 0
    while i < k:
        i *= 2
        count += 1
    lis.append(count)
result = 0
for i in lis:
    result += 1/n*0.5**i
print(result)

Submission status: Runtime Error

Solution code:
n,k = map(int, input())
lis = []
for i in range(1,N+1):
    count = 0
    while i < K:
        i *= 2
        count += 1
    lis.append(count)
result = 0
for i in lis:
    result += 1/n*0.5**i
print(result)

Submission status: Runtime Error

Solution code:
def d_even_relation_bfs():
    from collections import deque
    N = int(input())
    Edges = [[int(i) - 1 for i in input().split()] for j in range(N - 1)]  # 0-indexed

    graph = [[] for _ in range(N)]
    for u, v, w in Edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    distance_from_root = [0] * N  # 根は頂点 0 とする

    queue = deque([(-1, 0, 0)])  # 親と現在の頂点番号，根から親までの距離
    while queue:
        parent, current, distance = queue.pop()
        distance_from_root[current] = distance
        for next_vertex, dist in graph[current]:
            if parent != next_vertex:  # 木を「逆戻り」しない頂点だけ調べる
                queue.appendleft((current, next_vertex, distance + dist))
    ans = (1 if d % 2 == 0 else 0 for d in distance_from_root)
    return ' '.join(map(str, ans))

print(d_even_relation_bfs())

Submission status: Runtime Error

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  if a**count == n:
    return count
  else:
    return count+1

#############
# Main Code #
#############

N,K = IL()

l = [ int_log(K/i,2) if i<K else 0 for i in range(1,N+1)]
def format_float(v):
    s = str(v)
    if 'e' in s:
        i = s.index('e')
        exponent = int(s[i + 1:])
        mantissa = s[:i]
        if '.' not in mantissa:
            frac_len = 0
        else:
            frac_len = len(mantissa) - mantissa.index('.') - 1
        frac_len -= exponent
        if frac_len <= 0:
            s = str(int(v))
        else:
            s = '%.{int(frac_len)}f' % v
    if '.' not in s:
        s += '.0'
    return s
P(format_float(sum(pow(0.5,i) for i in l)/N))

Submission status: Runtime Error

Solution code:
from fractions import Fraction

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


def saikoro(x):
    y = Fraction(1, N)
    kakuritu = 1
    while 1 <= x and x <= K - 1:
        # 表
        x *= 2
        kakuritu *= 0.5
        if (x <= K):
            continue
        elif (x >= K):
            return kakuritu * float(y)
            break


count = 0
for i in range(1, N + 1):
    count += saikoro(i)
print(count)

Submission status: Runtime Error

Solution code:
from math import log2
n,k = map(int,input().split())
l = []
cnt = 0
for i in range(1,n+1):
    if i < k:
        l.append(int(log2(k/i))+1)
    else:
        cnt += 1
maxi = max(l)
preans = cnt * 2**maxi
for i in l:
    preans += 2**(maxi-i)
ans = preans / (n*2**maxi)
print('{:.20f}'.format(ans))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
for i in range(m):
    idx = a.index(max(a))
    a[idx] = int(a[idx] / 2)
print(sum(a))

Submission status: Runtime Error

Solution code:
[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
for i in range(m):
    a[-1] = int(a[-1] / 2)
    a.sort()
print(sum(a))

Submission status: Runtime Error

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


print(sum([(1/N)*(0.5)**math.ceil(math.log2(math.ceil(K/i))) if i<K else 1/N for i in range(1,N+1)])

Submission status: Runtime Error

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


print(sum([(1/N)*(0.5)**math.ceil(math.log2(max(K//i,1))) for i in range(1,N+1)])

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
beki_2 = list()
for i in range(15):
    beki_2.append(2**i)
    # print(beki_2)
eachother = [0]*N
ind = 0
i = 0
# print(beki_2)
f =0
while all:
    if(i == 0):
        j = 0
        while all:
            if(1*beki_2[j] >= K):
                ind = j
                # print("i")
                eachother[i] = ind
                break
            # print(j,beki_2[j])
            j+=1
        i+=1
    else:
        # print(i+1,beki_2[ind],ind)
        
        if(ind == 0):
            if(i+1>=K):
                eachother[i] = 0
                # print("i+1>=K")
                ind = 0
            else:
                for l in range(len(beki_2)):
                    if((i+1)*beki_2[l]>=K):
                        eachother[i] = 1
                        break
                ind = 1
            i+=1

        if((i+1)*beki_2[ind]<K):
            eachother[i] = ind+1
            i +=1
        # print((i+1)*beki_2[ind],ind,i)

    ind -= 1

    if(i == N or ind == -1):
        # print(i,N)
        break
sum_each = 0.0

for i in range(len(eachother)):
    sum_each+=beki_2[eachother[0]]/beki_2[eachother[i]]

# print(eachother[0:10])
print((1/N)*sum_each/beki_2[eachother[0]])

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
beki_2 = list()
for i in range(16):
    beki_2.append(2**i)
    # print(beki_2)
eachother = [0]*N
ind = 0
i = 0
# print(beki_2)
f =0
while all:
    if(i == 0):
        j = 0
        while all:
            if(1*beki_2[j] >= K):
                ind = j
                # print("i")
                eachother[i] = ind
                break
            # print(j,beki_2[j])
            j+=1
        i+=1
    else:
        # print(i+1,beki_2[ind])
        if((i+1)*beki_2[ind]<K):
            eachother[i] = ind+1
            i +=1
        # print((i+1)*beki_2[ind],ind,i)
        if(ind == 0):
            i+=1
        ind -= 1


    if(i == N or ind == 0):
        # print(i,N)
        break
sum_each = 0.0

for i in range(len(eachother)):
    sum_each+=beki_2[eachother[0]]/beki_2[eachother[i]]
print((1/N)*sum_each/beki_2[eachother[0]])
# print(eachother)
# (1/N)*()

Submission status: Runtime Error

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n,k = myinput()

ans = 0
import math
for i in range(n):
    m = i+1
    if m<k:
        x = math.ceil( math.log2(k/m) )
        ans += 1/n * ( (1/2)**x )
    else:
        ans += 1/n
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

p1 = max(N - K + 1, 0) / N
p2 = 0.
l2K = math.log2(K)
for k in range(1, min(K, N+1)):
    p2 += (1 / N) * (0.5) ** int(l2K - math.log2(k) + 1)

print(p1 + p2)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

from math import log2, ceil

def solve():
    n, k = MI()

    ans = 0
    m = ceil(log2(k))

    sm = 0
    v = 0
    for point in range(1, n+1):
        if 1 <= point < k:
            # さいころを振る
            # print(point)
            sm = sm + 1
            prob = 1
            for j in range(m+1):
                point = point * 2
                prob = prob / 2
                # print('  j+1', j+1, point)
                if point >= k:
                    # print(j)
                    ans = ans + prob
                    break
        else:
            # 無条件で勝利
            v = v + 1
    t = v / n
    print(ans * (1 - t) / sm + t)


if __name__ == '__main__':
    solve()