6008. Обратные треугольные числа

Треугольным называется число, которое может быть представлено множеством точек, упакованных в равносторонний треугольник с n точками на стороне. Далее приведены примеры треугольников с соответствующими треугольными числами:

Легко видеть, что треугольное число представляет собой аддитивный вариант факториала:

По заданному числу определите, является ли оно треугольным. Если ответ положительный, то определите количество точек на его стороне.

Например, 10 является треугольным с 4 точками на стороне, так как 10 = 4 + 3 + 2 + 1. Число 11 не является треугольным.

Вход. Каждая строка содержит целое число n (0 < n < 10⁹). Последняя строка содержит -1 и не обрабатывается.

Выход. Для каждого значения n определить, является ли оно треугольным числом. Если ответ утвердительный, то вывести в строке количество точек на стороне. Если ответ отрицательный, то вывести строку “bad”.

Пример входа	Пример выхода
55 1 91 587 499500 -1	Case 1: 10 Case 2: 1 Case 3: 13 Case 4: bad Case 5: 999

РЕШЕНИЕ

комбинаторика

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

Если k – длина стороны треугольника, то для полной его укладки требуется 1 + 2 + … + k = k * (k + 1) / 2 точек.

В наличии имеется n точек. Рассмотрим уравнение: k * (k + 1) / 2 = n. Запишем его в виде k² + k – 2n = 0. Дискриминант равен d = 1 + 8k. Для того чтобы число n было треугольным, необходимо чтобы дискриминант d был полным квадратом. Если это так, то ответом будет положительный корень уравнения

k =

Пример

Рассмотрим пример n = 55. Запишем уравнение: k² + k – 110 = 0.

Дискриминант равен d = 1 + 440 = 441. Положительный корень уравнения равен k = = (-1 + 21) / 2 = 10.

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

Последовательно обрабатываем тесты. Читаем входное значение n.

cs = 1;

while (scanf("%lld", &n), n != -1)

{

printf("Case %d: ", cs++);

Вычисляем дискриминант квадратного уравнения d.

d = 1 + 8 * n;

Проверяем, является ли дискриминант полным квадратом. Вычисляем sd = и проверяем равенство: sd * sd = d. Если дискриминант не является полным квадратом, то выводим “bad”.

sd = (long long)sqrt(d);

if (sd * sd != d)

{

printf("bad\n");

continue;

}

Вычисляем и выводим положительный корень уравнения.

k = (-1 + sqrt(d)) / 2;

printf("%lld\n", k);

}