Vasya and balls#4538

Vasya and balls (Editorial)

If $n$ is the side length of the triangle, then to completely fill it,

1 + 2 + ... + n = n \cdot (n + 1) /2

1 + 2 + ... + n = n \cdot (n + 1) / 2

balls are required.

Suppose there are $k$ balls available. To find the maximum possible $n$ , solve the equation

n \cdot (n + 1) /2 = k

n \cdot (n + 1) / 2 = k

and round the non-negative root down to the nearest integer.

Solve the quadratic equation:

n^{2} + n - 2 k = 0, d = 1 + 8 k, n = (- 1 + 1 + 8 k) /2

n^2 + n - 2k = 0, \\ d = 1 + 8k, n = (-1 + \sqrt{1 + 8k}) / 2

The answer will be $⌊(- 1 + 1 + 8 k) /2 ⌋$ \lfloor(-1 + \sqrt{1 + 8k}) / 2 \rfloor.

Algorithm implementation

Read the value of $k$ .

scanf("%d",&k);

Compute and print the answer.

n = int((-1 + sqrt(1.0 + 8*k)) / 2.0);
printf("%d\n",n);