10079. Разрезание пиццы

Какое максимальное количество кусков пиццы можно получить, сделав n прямолинейных разрезов ножом? Например, при n = 3 пиццу можно разрезать на 7 кусков.

Вход. Каждая строка содержит число прямолинейных разрезов ножом n (0 £ n £ 210000000). Признак конца входных данных n < 0.

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

Пример входа

5

10

-100

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

16

56

РЕШЕНИЕ

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

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

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

f(n) = f(n – 1) + n,

f(0) = 1

Решив рекуррентность, получим

f(n) = 1 + 1 + 2 + ... + n = 1 + = + +

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

Поскольку n £ 210000000, то объявим переменную n типа 64-битовое целое.

long long n;

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

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

printf("%lld\n",(n + n * n) / 2 + 1);