Вася і кулі#4538

Вася і кулі (Розбір)

Якщо $n$ — довжина сторони трикутника, то для його повного укладання потрібно

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

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

кульок.

Нехай у наявності є $k$ кульок. Щоб знайти максимальне можливе $n$ , розв'яжемо рівняння

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

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

і округлимо невід'ємний корінь вниз до найближчого цілого числа.

Розв'яжемо квадратне рівняння:

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

Відповіддю буде значення $⌊(- 1 + 1 + 8 k) /2 ⌋$ \lfloor(-1 + \sqrt{1 + 8k}) / 2 \rfloor.

Реалізація алгоритму

Читаємо вхідне значення $k$ .

scanf("%d",&k);

Обчислюємо і виводимо відповідь.

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