10784. Диагональ

Количество диагоналей у выпуклого n - угольника не менее N. Чему равно минимально возможное значение n?

Вход. Каждая входная стока содержит положительное целое число N (N £ 10¹⁵) – количество проведенных диагоналей. Значение N = 0 является концом входных данных и не обрабатывается.

Выход. Для каждого теста вывести его номер и минимально возможное число n сторон многоугольника.

Пример входа

10

100

1000

0

Пример выхода

Case 1: 7

Case 2: 16

Case 3: 47

РЕШЕНИЕ

математика + геометрия

Анализ алгоритма

Количество диагоналей выпуклого n – угольника равно n * (n – 3) / 2. Если n * (n – 3) / 2 = N, то n находим из квадратного уравнения n² – 3 * n – 2 * N = 0. Положительный корень уравнения равен

Остается округлить сверху вычисленное значение. Поскольку N £ 10¹⁵, то вычисления следует проводить, используя тип данных long long.

Пример

Рассмотрим второй тест. Для N = 100 получим

n = = 16

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

Читаем входные данные пока N > 0, вычисляем по формуле результат и выводим его с номером теста.

long long n, res;

int cs = 1;

while(scanf("%lld",&n), n > 0)

{

res = int(ceil((3 + sqrtl(9.0 + 8*n)) / 2));

printf("Case %d: %lld\n",cs,res);

cs++;

}