Minimal Üçbucaqlanma#11259

Minimal Üçbucaqlanma (Həll təhlili)

Tutaq ki, $(1, n)$ tərəfi olan üçbucaq üzərində düşünürük. Onun üçüncü zirvəsini $x$ ilə təmsil edək, onda üçbucaq $(1, n, x)$ (1, n, x) formasında olacaqdır.

Əgər $x = n - 1$ x = n - 1 olsa, sadəcə $(1, n, n - 1)$ (1, n, n - 1) üçbucağını atırıq və nəticədə $(n - 1)$ (n - 1) - bucaqlının qalan hissəsini üçbucaqlamağa davam edirik.

Əgər $1 < x < n - 1$ 1 < x < n - 1 olsa, onda $(n, x, k)$ (n, x, k) üçbucağına baxırıq, harada $x < k < n$ x < k < n.

Cüt üçbucaq $(1, x, n)$ (1, x, n) və $(n, x, k)$ (n, x, k) əvəzinə $(1, x, k)$ (1, x, k) və $(1, n, k)$ (1, n, k) cütünü dəyişirik. Üçbucaqların ümumi çəkisi azalır, çünki $x n + x nk > x k + nk$ xn + xnk > xk + nk. Qruplaşdırmadan sonra belə olur:

x (n - k) + nk (x - 1) > 0

x(n - k) + nk(x - 1) > 0

Bərabərlik düzgündür, çünki $n - k > 0$ n - k > 0 və $x - 1 > 0$ x - 1 > 0.

Buradan belə nəticəyə gəlirik ki, $(1, x, n)$ (1, x, n) üçbucağı $(1, k, n)$ (1, k, n) ilə əvəz etmək daha sərfəlidir, harada $k > x$ k > x. Bu səbəblə, optimal seçim $x = n - 1$ x = n - 1 olacaqdır. Minimum çəki üçbucaqların bütün diaqonallarını 1-ci zirvədən çəkməklə əldə edilir.

1-dəki bütün üçbucaqların ümumi çəkisi belədir:

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 + ... + 1 \cdot (n - 1) \cdot n = i = 2 \sum n - 1 i (i + 1)

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 + ... + 1 \cdot (n - 1) \cdot n = \sum_{i = 2}^{n-1} i(i + 1)

Misal

Birinci testdə, zirvələri $1, 2, 3$ olan üçbucaq verilmişdir. Onun çəkisi $1 \cdot 2 \cdot 3 = 6$ 1 \cdot 2 \cdot 3 = 6-yə bərabərdir.

İkinci testdə, zirvələri $1, 2, 3, 4$ 1, 2, 3, 4 olan kvadrat verilmişdir. Minimum çəki $(1, 3)$ diaqonallı üçbucaqlamada əldə edilir:

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18

Alqoritmin Reallaşdırılması

Giriş məlumatlarını oxuyuruq.

scanf("%d", &n);

Cavabı hesablayırıq.

res = 0;
for (i = 2; i < n; i++)
  res += 1ll * i * (i + 1);

Cavabı çıxışa yazırıq.

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