Подсчет треугольников (Editorial)

Обозначим через $T(n)$ количество различных треугольников, которые можно построить из $n$ стержней.

Условие существования треугольника. Пусть выбраны три стержня с длинами a < b < c. Тогда необходимое и достаточное условие существования треугольника имеет вид:

Поскольку $c$ — наибольшая сторона, остальные неравенства выполняются автоматически.

Вычислим несколько первых значений функции:

• T(3) = 0, из стержней с длинами $1,2$ и $3$ составить треугольник нельзя;

• T(4) = 1, треугольник (2, 3, 4);

• T(5) = 3, треугольники (2, 3, 4), (2, 4, 5), (3, 4, 5);

• T(6) = 7, треугольники (2, 3, 4), (2, 4, 5), (3, 4, 5), (4, 5, 6), (3, 5, 6), (2, 5, 6), (3, 4, 6);

Рекуррентный подход. Заметим, что множество всех треугольников $T(n)$ можно разбить на два подмножества:

• треугольники, не содержащие сторону $n$ (их T(n - 1)),

• треугольники, содержащие сторону $n$.

Обозначим множество треугольников, содержащих сторону $n$, через $S(n)$. Тогда:

Например

Тогда

Подсчет S(n). Рассмотрим треугольники вида (a, b, n), где a < b < n. Условие существования треугольника:

Зафиксируем $b$ и найдём возможные $a$:

При этом a < b, следовательно:

Число подходящих значений $a$ равно:

Суммируем по всем допустимым $b$, для которых 2b - n - 1 > 0, то есть:

Пример. Вычислим значение $S(6)$, то есть найдем все треугольники вида (a, b, 6).

Необходио выполнение условия: b > (6 + 1) / 2 = 3. Учитывая что b < 6, возможными значениями для $b$ будут $4$ и $5$.

• При b = 4: 6 - 4 < a < 4, 2 < a < 4, получаем тройку (3, 4, 6).

• При b = 5: 6 - 5 < a < 5, 1 < a < 5, получаем тройки (2, 5, 6), (3, 5, 6), (4, 5, 6).

Таким образом,

Вычисление |S(n)|.

Случай 1: $n$ чётное. Пусть n = 2k. Тогда: b > \frac{2k + 1}{2} = k + \frac{1}{2}. Следовательно, значение $b$ может принимать значения: k + 1, k + 2, ..., 2k - 1 (так как b < n, то b < 2k и наибольшее значение $b$ может быть равным 2k - 1).

Теперь суммируем значения 2b - n - 1 = 2b - 2k - 1 для всех b~(k + 1 \le b \le 2k - 1).

Получаем:

По формуле арифметической прогрессии:

Случай 2: $n$ нечётное. Пусть n = 2k + 1. Тогда: b > \frac{2k + 2}{2} = k + 1. Следовательно, значение $b$ может принимать значения: k + 2, k + 3, ..., 2k - 1 (так как b < n, то b < 2k + 1 и наибольшее значение $b$ может быть равным $2k$).

Теперь суммируем значения 2b - n - 1 = 2b - 2k - 2 для всех b~(k + 2 \le b \le 2k).

Получаем:

По формуле арифметической прогрессии:

Таким образом получим рекуррентность:

• при четном $n$ имеем: T(n) = T(n - 1) + \frac{(n - 2)^2}{4};

• при нечетном $n$ имеем: T(n) = T(n - 1) + \frac{n - 1}{2} \cdot \frac{n - 3}{2};

Значение $T(n)$ можно также выразить в явном виде:

Последовательность $T(n)$ имеет производящую функцию

Пример

Построим множество $S(7)$.

• Вместе с числом $6$ могут быть числа 2, 3, 4, 5 — образуя тройки (2, 6, 7), (3, 6, 7), (4, 6, 7), (5, 6, 7);

• Вместе с числом $5$ могут быть числа $3,4$ — образуя тройки (3, 5, 7), (4, 5, 7);

Поскольку $S(7)$ содержит 2 + 4 = 6 элементов, то T(7) = T(6) + |S(7)| = 7 + 6 = 13.

Первые значения функции $T(n)$ имеют вид:

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

Объявим массив $t$ для хранения результатов.

#define MAX 1000001
long long t[MAX];

Основная часть программы. Заполняем массив $t$.

memset(t, 0, sizeof(t));
for(i = 4; i < MAX; i++)
  if (i % 2 == 0) t[i] = t[i - 1] + (i - 2) / 2 * (i - 2) / 2;
  else t[i] = t[i - 1] + (i - 1) * (i - 3) / 4;

Последовательно обрабатываем запросы.

while(scanf("%lld",&n), n >= 3)
  printf("%lld\n", t[n]);

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

Реализация функции $T(n)$.

long long T(long long n)
{
  if (n % 2) return (n - 1) * (n - 3) * (2 * n - 1) / 24;
  return n * (n - 2) * (2 * n - 5) / 24;
}

Основная часть программы. Для каждого входного значения $n$ выводим $T(n)$.

while(scanf("%lld",&n), n >= 3)
  printf("%lld\n",T(n));