Triangle Counting#8616

Triangle Counting (Editorial)

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

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

a + b > c

a + b > c

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

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

$T (3) = 0$ T(3) = 0, из стержней с длинами $1, 2$ и $3$ составить треугольник нельзя;
$T (4) = 1$ T(4) = 1, треугольник $(2, 3, 4)$ (2, 3, 4);
$T (5) = 3$ T(5) = 3, треугольники $(2, 3, 4), (2, 4, 5), (3, 4, 5)$ (2, 3, 4), (2, 4, 5), (3, 4, 5);
$T (6) = 7$ T(6) = 7, треугольники $(2, 3, 4), (2, 4, 5), (3, 4, 5), (4, 5, 6), (3, 5, 6), (2, 5, 6), (3, 4, 6)$ (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)$ T(n - 1)),
треугольники, содержащие сторону $n$ .

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

T (n) = T (n - 1) + ∣ S (n) ∣

T(n) = T(n - 1) + |S(n)|

Например

S (6) = {(4, 5, 6), (3, 5, 6), (2, 5, 6), (3, 4, 6)}

S(6) = \{ (4, 5, 6), (3, 5, 6), (2, 5, 6), (3, 4, 6) \}

Тогда

T (6) = T (5) \cup S (6)

T(6) = T(5) \cup S(6)

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

a + b > n

a + b > n

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

a > n - b

a > n - b

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

n - b < a < b

n - b < a < b

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

b - (n - b + 1) = 2 b - n - 1

b - (n - b + 1) = 2b - n - 1

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

b > \frac{n + 1}{2}

b > \frac{n + 1}{2}

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

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

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

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

S (6) = {(3, 4, 6), (2, 5, 6), (3, 5, 6), (4, 5, 6)}

S(6) = \{ (3, 4, 6), (2, 5, 6), (3, 5, 6), (4, 5, 6) \}

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

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

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

Получаем:

∣ S (n) ∣ = 1 + 3 + 5 + ... + (n - 3)

|S(n)| = 1 + 3 + 5 + ... + (n - 3)

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

∣ S (n) ∣ = \frac{1 + ( n - 3 )}{2} \cdot \frac{n - 2}{2} = \frac{( n - 2 ) ^{2}}{4}

|S(n)| = \frac{1 + (n - 3)}{2} \cdot \frac{n - 2}{2} = \frac{(n-2)^2}{4}

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

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

Получаем:

∣ S (n) ∣ = 2 + 4 + 6 + ... + (n - 3)

|S(n)| = 2 + 4 + 6 + ... + (n - 3)

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

∣ S (n) ∣ = \frac{2 + ( n - 3 )}{2} \cdot \frac{n - 3}{2} = \frac{( n - 1 ) ( n - 3 )}{4}

|S(n)| = \frac{2 + (n - 3)}{2} \cdot \frac{n - 3}{2} = \frac{(n - 1) (n - 3)}{4}

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

при четном $n$ имеем: $T (n) = T (n - 1) + \frac{( n - 2 ) ^{2}}{4}$ 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 - 1) + \frac{n - 1}{2} \cdot \frac{n - 3}{2};

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

T (n) = ⎩ ⎨ ⎧ \frac{1}{24} n (n - 2) (2 n - 5), \frac{1}{24} (n - 1) (n - 3) (2 n - 1), если n чётно, если n нечётно .

T(n) = \begin{cases} \dfrac{1}{24}\, n(n - 2)(2n - 5), & \text{если } n \text{ чётно}, \\ \dfrac{1}{24}\, (n - 1)(n - 3)(2n - 1), & \text{если } n \text{ нечётно}. \end{cases}

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

f (x) = \frac{x ^{4}}{( 1 - x ) ^{3} ( 1 - x ^{2} )} = x^{4} + 3 x^{5} + 7 x^{6} + 13 x^{7} + ...

f(x)=\frac{x^4}{(1-x)^3 (1-x^2 )} = x^4 + 3x^5 + 7x^6 + 13x^7 + ...

Пример

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

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

Поскольку $S (7)$ содержит $2 + 4 = 6$ 2 + 4 = 6 элементов, то $T (7) = T (6) + ∣ S (7) ∣ = 7 + 6 = 13$ 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));