/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1000 点
問題文
りんごさんはクッキーを焼いています。
りんごさんははじめ、1 秒間に 1 枚のクッキーを焼くことができます。
りんごさんはクッキーを食べることができます。 まだ食べていないクッキーが全部で x 枚あるとき、りんごさんはそれらをすべて食べることにより、1 秒間に焼くことのできるクッキーの枚数がちょうど x 枚になります。 クッキーを一部だけ食べることはできず、食べるときはすべて食べなければなりません。 クッキーを食べるためには個数にかかわらず A 秒の時間がかかり、その間はクッキーを焼くことができません。 また、クッキーは 1 秒ごとに同時に焼きあがるため、例えば 0.5 秒で x/2 枚のクッキーを焼くというようなことはできません。
りんごさんは N 枚のクッキーをおばあさんにプレゼントしたいと思っています。 りんごさんがまだ食べていないクッキーを N 枚以上用意するためにかかる時間の最小値を求めてください。
制約
- 1≦N≦10^{12}
- 0≦A≦10^{12}
- A は整数である。
部分点
- N≦10^6 かつ A≦10^6 を満たすデータセットに正解した場合は、500 点が与えられる。
- 追加制約のないデータセットに正解した場合は、上記とは別に 500 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N A
出力
りんごさんがまだ食べていないクッキーを N 枚以上用意するためにかかる時間の最小値を出力せよ。
入力例 1
8 1
出力例 1
7
以下のように行動すると、7 秒で 8 枚のクッキーを用意することができます。
- 1 秒後：1 枚のクッキーが焼きあがる。
- 2 秒後：1 枚のクッキーが焼きあがり、合計枚数が 2 枚となる。ここで、2 枚のクッキーをすべて食べる。
- 3 秒後：クッキーを食べ終わり、1 秒間に 2 枚のクッキーを焼くことができるようになる。
- 4 秒後：2 枚のクッキーが焼きあがる。
- 5 秒後：2 枚のクッキーが焼きあがり、合計枚数が 4 枚となる。
- 6 秒後：2 枚のクッキーが焼きあがり、合計枚数が 6 枚となる。
- 7 秒後：2 枚のクッキーが焼きあがり、合計枚数が 8 枚となる。
入力例 2
1000000000000 1000000000000
出力例 2
1000000000000
入力例 3
123456 7
出力例 3
78
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