Problem:


Score : 1000 points

Problem Statement

Rng is baking cookies.

Initially, he can bake one cookie per second.

He can also eat the cookies baked by himself.
When there are x cookies not yet eaten, he can choose to eat all those cookies. After he finishes eating those cookies, the number of cookies he can bake per second becomes x. Note that a cookie always needs to be baked for 1 second, that is, he cannot bake a cookie in 1/x seconds when x > 1.
When he choose to eat the cookies, he must eat all of them; he cannot choose to eat only part of them.
It takes him A seconds to eat the cookies regardless of how many, during which no cookies can be baked.

He wants to give N cookies to Grandma.
Find the shortest time needed to produce at least N cookies not yet eaten.

Constraints

1≦N≦10^{12}

0≦A≦10^{12}

A is an integer.

Partial Score

500 points will be awarded for passing the test set satisfying N≦10^6 and A≦10^6.

Additional 500 points will be awarded for passing the test set without additional constraints.

Input

The input is given from Standard Input in the following format:

N A

Output

Print the shortest time needed to produce at least N cookies not yet eaten.

Sample Input 1

8 1

Sample Output 1

7

It is possible to produce 8 cookies in 7 seconds, as follows:

After 1 second: 1 cookie is done.

After 2 seconds: 1 more cookie is done, totaling 2. Now, Rng starts eating those 2 cookies.

After 3 seconds: He finishes eating the cookies, and he can now bake 2 cookies per second.

After 4 seconds: 2 cookies are done.

After 5 seconds: 2 more cookies are done, totaling 4.

After 6 seconds: 2 more cookies are done, totaling 6.

After 7 seconds: 2 more cookies are done, totaling 8.

Sample Input 2

1000000000000 1000000000000

Sample Output 2

1000000000000



Sample input:
8 1


Sample output:
7

Submission status: Accepted

Solution code:
def examA():
    H, W = LI()
    S = [LSI() for _ in range(H)]
    Alpha = [chr(ord('A') + i) for i in range(26)]
    for i in range(H):
        for j in range(W):
            if S[i][j]=="snuke":
                ans = str(Alpha[j]) + str(i+1)
    print(ans)
    return

def examB():
    N = I()
    ans = []
    cur = int((N*2-1)**0.5)+1
    ansC = (cur+1)*cur//2
    neg = ansC-N
    if neg>cur:
        cur -=1
        ansC = (cur + 1) * cur // 2
        neg = ansC - N
    for i in range(1,cur+1):
        if i!=neg:
            ans.append(i)
    for v in ans:
        print(v)
#    print(cur,neg)
    return

def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    que = deque()
    que.append(e)
    len = [10**9]*n
    len[e] = 0
    while que:
        now = que.popleft()
        nowlen = len[now]
        for ne in fordfs[now]:
            if len[ne] == 10**9:
                len[ne] = nowlen+1
                que.append(ne)
    return len
def examC():
    N, M = LI()
    V = [[]for _ in range(N+M)]
    for i in range(N):
        L = LI()
        for k in range(1,L[0]+1):
            V[i].append(L[k]+N-1)
            V[L[k]+N-1].append(i)
    length = bfs(N+M,0,V)
    ans = "YES"
    for i in length[:N]:
        if i==10**9:
            ans = "NO"
    print(ans)
    return

def examD():
    N, M = LI()
    X = LI(); maxX = max(X)+1
    dx = defaultdict(int)
    dm = [set()for _ in range(M)]
    d = defaultdict(int)
    for x in X:
        dx[x] +=1
        d[x%M] +=1
        dm[x%M].add(x)
    ans = 0
#    print(d); print(dx); print(dm)
    ans +=d[0]//2
    d[0] = 0
    for i in range(1,1+M//2):
        cur = min(d[i],d[M-i])
        ans +=cur
        d[i] -=cur; d[M-i] -=cur
#    print(ans); print(d)
    for i in d.keys():
        for j in dm[i]:
            cur = min(dx[j]//2,d[i]//2)
            d[i] -= cur * 2
            ans += cur
            if d[i]<=1:
                break
    print(ans)
    return

def caneat(x,A,n):
    cur = n - A*x
    if cur<=0:
        return 1
    l = cur//(x+1); r = cur%(x+1)
    if l==0:
        return 1
    now = pow(l,(x-r+1))*pow((l+1),r)
    return now
def ternarySearch(A,n,e):
    #何回喰うか
    fr, to = 0, e
    while to - fr > 2:
        x1, x2 = (2 * fr + to)//3, (2 * to + fr)//3
        f1, f2 = caneat(x1,A,n), caneat(x2,A,n)
        if f1 > f2:
            to = x2
        elif f1 < f2:
            fr = x1
        else:
            fr, to = x1, x2
    return max(caneat(fr,A,n),caneat(fr+1,A,n),caneat(to,A,n))
def examE():
    N, A = LI()
    l = 0; r = N+1
    while(r-l>1):
        now = (l+r)//2
        maxE = min(40,now//(A+1))
        cur = ternarySearch(A,now,maxE)
        if N<=cur:
            r = now
        else:
            l = now
#        print(l,r,cur)
#    print(l,r)
    ans = r
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examE()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,A = map(int,read().split())

"""
最適解の構造を観察する。
・最後のトドメ以外に関しては、「コストn+A払って倍率をn倍する」
・nとして現れるのは2種まで
・結局、nをx回、n+1をy回という形で、パラメータn,x,yで書ける（x\geq 1とする）
・最終枚数は、n^x(n+1)^y、これがN以上になって欲しい
・コストは、A(x+y-1) + nx + (n+1)y
・x+yを固定するごとに解く
"""

def F(K):
    # x+y = K
    # n^K <= N < (n+1)^K
    n = int(N**(1/K))
    while (n-1)*n**(K-1) > N:
        n -= 1
    while n * (n+1)**(K-1) < N:
        n += 1
    # n^x(n+1)^y >= N, yを最小にとる。面倒なので全探索
    for y in range(K):
        x = K-y
        if n**x * (n+1)**y >= N:
            break
    cost = A*(K-1) + n*x + (n+1)*y
    return cost

answer = min(F(K) for K in range(1,50))
print(answer)

Submission status: Accepted

Solution code:
import math


def main():
    N, A = map(int, input().split())
    ans = float("inf")
    for i in range(41):
        x = int(math.pow(N, 1/(i+1)))
        k = 0
        while x**(i+1-k) * (x+1)**k < N:
            k += 1
        y = x * (i+1-k) + (x+1) * k + A * i
        ans = min(ans, y)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

N, A = map(int, raw_input().split())
ans = 10 ** 18

for num in range(1, 65):
    p = int(N ** (1.0 / num))
    ls = [p] * num
    pos = 0
    while True:
        cnt = 1
        for p in ls:
            cnt *= p
        if cnt >= N:
            break
        ls[pos] += 1
        pos += 1
        pos %= num
    ans = min(ans, sum(ls) + A * (num - 1))
print ans

Submission status: Accepted

Solution code:
# seishin.py
N, A = map(int, input().split())

ans = N
if N > 1:
    for k in range(1, 41):
        left = 0; right = N+1
        while left+1 < right:
            mid = (left + right) // 2
            if mid**(k+1) < N:
                left = mid
            else:
                right = mid
        m = right
        v = (m-1)**(k+1)
        for i in range(k+1):
            v //= m-1
            v *= m
            if N <= v:
                ans = min(ans, A*k + (m-1)*(k+1) + (i+1))
                break
print(ans)

Submission status: Accepted

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

ans = N

for k in range(50):
    left, right = 1, int(pow(N, 1/(k+1))) + 1
    while left + 1 < right:
        mid = (left + right) >> 1
        if mid ** (k+1) >= N:
            right = mid
        else:
            left = mid
    for i in range(k+1):
        if ((right - 1) ** i) * (right ** (k+1 - i)) >= N:
            ans = min(ans, A * k + i * (right - 1) + (k+1 - i) * right)
print(ans)

Submission status: Accepted

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

def pow(a, b):
    if b == 1:return a
    if b%2 == 0: return pow(a*a, int(b/2))
    return a*pow(a*a, int(b/2))

def binaryOne(n, multi):
    l, r = 0, n
    mid = (l + r)/2    
    while r - l > 1:
        if pow(mid, multi) >= n:
            r = mid
        else:
            l = mid
        mid = (r + l)/2
    return r;


def binaryTwo(n, maxi, multi):
    l, r = 0, multi
    mid = (l + r)/2
    while r - l > 1:
        if pow(maxi, (multi - mid))*pow(maxi - 1, mid) >= n:
            l = mid
        else:
            r = mid
        mid = (r + l)/2;
    return l

n, a = map(int,raw_input().split(" "))
ans = 1e18
for i in xrange(0, 40):
    maxi = binaryOne(n, i + 1);
    subt = binaryTwo(n, maxi, i + 1)
    ans = min(ans, a*i + maxi*(i + 1) - subt)
    
print ans

Submission status: Accepted

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

ans = N

for i in range(1, 50):
    ok = 10 ** 20
    ng = 0

    while ok - ng > 1:
        mid = (ok + ng) // 2
        prod = 1
        for j in range(i):
            prod *= (mid + j) // i
        if prod >= N:
            ok = mid
        else:
            ng = mid

    ans = min(ans, A * (i - 1) + ok)

print(ans)

Submission status: Runtime Error

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

ans=N
for n in range(1,41):
    for i in range(2*n,N**(1/n)+100):
        test=i+n*A
        q=i//n
        r=i%n
        prod=pow(q,n-r)*pow(q+1,r)
        test+=(N-1)//prod+1
        ans=min(ans,test)

print(ans)

Submission status: Runtime Error

Solution code:
n,a = map(int,input().split())
if n == 1:
  print(1)
  exit()
l = -1
r = 10**12+1
#n <= x**(k-i)*(x-1)**iのk-iを返す
def border(x,k):
  if k >= 40:
    return (n-1).bit_length()
  else:
    L = 0
    R = k
    while L+1 < R:
      M = (L+R)//2
      if x**(k-M)*(x-1)**(M) < n:
        R = M
      else:
        L = M
    return k-L
def sec(k):
  if k >= 40:
    x = 2
  else:
    y = int(n**(1/k))+1
    if (y-1)**k < n <= y**k:
      x = y
    elif y**k < n <= (y+1)**k:
      x = y+1
    elif (y-2)**k < n <= (y-1)**k:
      x = y-1
  b = border(x,k)
  return (x+a)*k-(k-b)

while l+2 < r:
  ml = (l*2+r)//3
  mr = (l+r*2)//3
  if sec(ml) < sec(mr):
    r = mr
  else:
    l = ml
print(sec(l+1)-a)

Submission status: Runtime Error

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


def check(x):
    if x - 50*A >= 100:
        return N+1
    right = x//A
    left = 1
    while abs(right - left) > 2:
        med1 = (left*2+right)//3
        med2 = (left+right*2)//3
        if calc(med1, x-(med1-1)*A) < calc(med2, x-(med2-1)*A):
            left = med1
        else:
            right = med2
    
    res = 0
    for l in range(left, right+1):
        cl = calc(l, x-(l-1)*A)
        if res < cl:
            res = cl
    return res
    
    
def calc(k, c):
    return pow(c//k+1, c%k)*pow(c//k, k-c%k)

N, A = map(int, readline().split())

ok = N
ng = 0
while abs(ok-ng)>1:
    med = (ok+ng)//2
    if check(med) >= N:
        ok = med
    else:
        ng = med
print(ok)

Submission status: Runtime Error

Solution code:
# seishin.py
N, A = map(int, input().split())

ans = N
for k in range(1, 41):
    left = 0; right = N+1
    while left+1 < right:
        mid = (left + right) // 2
        if mid**(k+1) < N:
            left = mid
        else:
            right = mid
    m = right
    v = (m-1)**(k+1)
    for i in range(k+1):
        v //= m-1
        v *= m
        if N <= v:
            ans = min(ans, A*k + (m-1)*(k+1) + (i+1))
            break
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from math import ceil
N, A = [int(i) for i in input().split()]
if N > 10 ** 6 or A > 10 ** 6:
    print(-1)
    sys.exit()
dp = [float("inf")] * (N+1)
dp[1] = 0
for i in range(1, N//2+1):
    for n, j in enumerate(range(i+i, N+1, i), start=2):
        dp[j] = min(dp[j], dp[i]+n+A)
ans = min(dp[i]+ceil(N/i) for i in range(1, N//2+1), default=N)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from math import ceil
N, A = [int(i) for i in input().split()]
if N > 10 ** 6 or A > 10 ** 6:
    raise
dp = [float("inf")] * (N+1)
dp[1] = 0
ans = float("inf")
for i in range(1, N//2+1):
    for n, j in enumerate(range(i+i, N+1, i), start=2):
        dp[j] = min(dp[j], dp[i]+n+A)
ans = min(dp[i]+ceil(N/i) for i in range(1, N+1))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from math import ceil
if N > 10 ** 6 or A > 10 ** 6:
    print(-1)
    sys.exit()
N, A = [int(i) for i in input().split()]
dp = [float("inf")] * N
dp[1] = 0
for i in range(1, N//2+1):
    for n, j in enumerate(range(i+i, N//2+1, i), start=2):
        dp[j] = min(dp[j], dp[i]+n+A)
ans = min(dp[i]+ceil(N/i) for i in range(1, N//2+1))
print(ans)

Submission status: Runtime Error

Solution code:
# encoding: utf-8
n, a = map(int, raw_input().split())
if n>10**7 or a >= 10**7:
    exit(1)

memo = [-1]*(n+1)
# 残りx個を貯めるために最小の時間を返す予定
def dfs(x):
    if x == 0:
        return 0
    if memo[x] != -1:
        return memo[x]
    i = 0
    res = x
    for i in xrange(2, x+1):
        # i-sec待つ
        res = min(res, dfs((x+i-1)/i)+a+i)
    memo[x] = res
    return memo[x]
print dfs(n)

Submission status: Runtime Error

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

(N, A) = reads()

assert(N <= 10**6 and A <= 10**6)

c = [0] * (N+3)

for i in range(A+1):
  c[i] = i
  if c[i] >= N:
    print(i)
    # print(c[:i+1])
    exit()

for i in range(A+1, N+2):
  c[i] = max(i, max(c[j]*(i-j-A) for j in range(i-A)))
  if c[i] >= N:
    print(i)
    # print(c[:i+1])
    exit()

Submission status: Runtime Error

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

(N, A) = reads()

assert(N <= 10**6 and A <= 10**6)

c = [0]*(N+3)

for i in range(A+1):
  c[i] = i
  if c[i] >= N:
    print(i)
    # print(c[:i+1])
    exit()

for i in range(A+1, N+3):
  c[i] = max(i, max(c[j]*(i-j-A) for j in range(i-A)))
  if c[i] >= N:
    print(i)
    # print(c[:i+1])
    exit()