CF985D.Sand Fortress

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are going to the beach with the idea to build the greatest sand castle ever in your head! The beach is not as three-dimensional as you could have imagined, it can be decribed as a line of spots to pile up sand pillars. Spots are numbered 11 through infinity from left to right.

Obviously, there is not enough sand on the beach, so you brought nn packs of sand with you. Let height hih_{i} of the sand pillar on some spot ii be the number of sand packs you spent on it. You can't split a sand pack to multiple pillars, all the sand from it should go to a single one. There is a fence of height equal to the height of pillar with HH sand packs to the left of the first spot and you should prevent sand from going over it.

Finally you ended up with the following conditions to building the castle:

  • h1<=Hh_{1}<=H : no sand from the leftmost spot should go over the fence;
  • For any hihi+1<=1|h_{i}-h_{i+1}|<=1 : large difference in heights of two neighboring pillars can lead sand to fall down from the higher one to the lower, you really don't want this to happen;
  • : you want to spend all the sand you brought with you.

As you have infinite spots to build, it is always possible to come up with some valid castle structure. Though you want the castle to be as compact as possible.

Your task is to calculate the minimum number of spots you can occupy so that all the aforementioned conditions hold.

输入格式

The only line contains two integer numbers nn and HH ( 1<=n,H<=10181<=n,H<=10^{18} ) — the number of sand packs you have and the height of the fence, respectively.

输出格式

Print the minimum number of spots you can occupy so the all the castle building conditions hold.

输入输出样例

  • 输入#1

    5 2
    

    输出#1

    3
    
  • 输入#2

    6 8
    

    输出#2

    3
    

说明/提示

Here are the heights of some valid castles:

  • n=5,H=2,[2,2,1,0,...],[2,1,1,1,0,...],[1,0,1,2,1,0,...]n=5,H=2,[2,2,1,0,...],[2,1,1,1,0,...],[1,0,1,2,1,0,...]
  • n=6,H=8,[3,2,1,0,...],[2,2,1,1,0,...],[0,1,0,1,2,1,1,0...]n=6,H=8,[3,2,1,0,...],[2,2,1,1,0,...],[0,1,0,1,2,1,1,0...] (this one has 55 spots occupied)

The first list for both cases is the optimal answer, 33 spots are occupied in them.

And here are some invalid ones:

  • n=5,H=2,[3,2,0,...],[2,3,0,...],[1,0,2,2,...]n=5,H=2,[3,2,0,...],[2,3,0,...],[1,0,2,2,...]
  • n=6,H=8,[2,2,2,0,...],[6,0,...],[1,4,1,0...],[2,2,1,0,...]n=6,H=8,[2,2,2,0,...],[6,0,...],[1,4,1,0...],[2,2,1,0,...]
首页