Sand Fortress
Contest: Educational Codeforces Round 44 (Rated for Div. 2)
Difficulty rating: 2100
Tags: binary search, constructive algorithms, math

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 1 through infinity from left to right.

Obviously, there is not enough sand on the beach, so you brought n packs of sand with you. Let height hi of the sand pillar on some spot i 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 H 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 ≤ H: no sand from the leftmost spot should go over the fence;
- For any $$i \in [1; \infty)$$ |hi - hi + 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;
- $$\sum_{i=1}^{\infty} h_i = n$$: 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.

Input format:
The only line contains two integer numbers n and H (1 ≤ n, H ≤ 1018) — the number of sand packs you have and the height of the fence, respectively.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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 = 6, H = 8, [3, 2, 1, 0, ...], [2, 2, 1, 1, 0, ...], [0, 1, 0, 1, 2, 1, 1, 0...] (this one has 5 spots occupied)

The first list for both cases is the optimal answer, 3 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 = 6, H = 8, [2, 2, 2, 0, ...], [6, 0, ...], [1, 4, 1, 0...], [2, 2, 1, 0, ...]

Example input:
5 2

Example output:
3

Example input:
6 8

Example output:
3

Editorial:
Let's consider the optimal answer to always look like h1 ≤ h2 ≤ ... ≤ hk ≥ hk + 1 ≥ ...
k will be the leftmost position of a pillar with maximum height. We will heavily use the fact that all integers from 1 to hk - 1 appear in this sequence to the right of k.
If you are able to construct any answer, it is easy to rearrange it to this pattern: select the leftmost maximum k, sort [1..k - 1] in non-decreasing order and [k + 1..∞) in non-increasing order. Sorted sequence will also be valid.
Let a pyramid of height k be such a valid castle that it occupies exactly 2k - 1 consecutive spots and 1 = h1 < h2 < ... < hk > hk + 1 > ... > h2k - 1 = 1. Exactly k2 sand packs are required to build it.
At first let's solve the problem without even touching the fence. This won't always give the minimal answer but it'll help us further. Given some k you can build the pyramid of height k and get n - k2 sand packs left over. This can fit in exactly $$\left\lceil \frac{n-k^2}{k} \right\rceil$$ pillars (you can place any pillar of height  ≤ k next to some pillar of the same height). That way we see that $$ans(k) = 2k - 1 + \left\lceil \frac{n-k^2}{k} \right\rceil$$.
This function is non-increasing, let's show that for any k from 2 to $$\sqrt{n}$$ ans(k) - ans(k - 1) is non-positive.
ans(k) - ans(k - 1) = $$2k-1+\left\lceil \frac{n-k^{2}}{k} \right\rceil - 2 \cdot (k-1) + 1-\left\lceil \frac{n-(k-1)^{2}}{k-1} \right\rceil$$ = $$2 + \left\lceil \frac{n - k^2}{k} \right\rceil - \left\lceil \frac{n - (k-1)^2}{k-1} \right\rceil$$ = $$2 + \left\lceil \frac{n}{k} \right\rceil - k - \left\lceil \frac{n}{k-1} \right\rceil + (k-1)$$ = $$1 + \left\lceil \frac{n}{k} \right\rceil - \left\lceil \frac{n}{k-1} \right\rceil$$ = $$\left\lceil \frac{n+k}{k} \right\rceil - \left\lceil \frac{n}{k-1} \right\rceil$$ = $$\left\lceil \frac{(n+k)(k-1)}{k(k-1)} \right\rceil - \left\lceil \frac{nk}{k(k-1)} \right\rceil$$.
$$\left\lceil \frac{(n+k)(k-1)}{k(k-1)} \right\rceil \leq \left\lceil \frac{nk}{k(k-1)} \right\rceil$$ $$\text{The formula used to produce the text is not provided in the image.}$$ (n + k)(k - 1) ≤ nk + k(k - 1) - 1 $$\text{The formula used to produce the text is not provided in the image.}$$ nk - n + k2 - k ≤ nk + k2 - k - 1 $$\text{The formula used to produce the text is not provided in the image.}$$ n ≥ 1.
Now we can show that it is always optimal to push the initial pyramid to the left as far as possible, probably removing some pillars on positions less than k. That way the leftmost pillar will have height h1 = min(k, H). The total number of sand packs required to build it is $$k^2 - \frac{h_1 \cdot (h_1 - 1)}{2}$$. This pattern will also include all the integers from 1 to k and will have the minimal width you can achieve. Monotonicity of this function can be proven in the similar manner.
Finally, the answer can be calculated using the following algorithm:
1. Find the maximum k such that $$k^2 - \frac{h_1 \cdot (h_1 - 1)}{2} \leq n$$, where h1 = min(k, H). Solve the equation or just do the binary search;
2. Output the width of resulting truncated pyramid plus the minimal number of additional pillars it will take to distribute leftover sand packs.
You should also take into consideration the upper bound on k to avoid multiplying huge numbers. It's about $$\sqrt{2n}$$, so 64-bit integer type will be enough for all the calculations.
Overall complexity: O(1) or $${\mathcal {O}}(\log n)$$.