Minimal Üçbucaqlanma

Sizə $n$ zirvələri olan düzgün çoxbucaqlı verilir, zirvələr $1$-dən $n$-ə əks istiqamətdə nömrələnib.

Üçbucaqlanma bu çoxbucaqlının üçbucaqlara bölünməsidir, belə ki:

• hər bir üçbucağın zirvələri başlanğıc çoxbucaqlının zirvəsidir;

• heç bir iki üçbucağın kəsişmə sahəsi müsbət deyil;

• bütün üçbucaqların birləşməsinin sahəsi başlanğıc çoxbucaqlının sahəsinə bərabərdir.

Üçbucaqlanmanın çəkisi, ona daxil olan üçbucaqların çəki cəmi ilə təyin olunur, burada üçbucağın çəkisi onun zirvələrinin etiketlərinin hasilinə bərabərdir.

Verilmiş çoxbucaqlının bütün mümkün üçbucaqlanmaları arasında minimal çəkini tapın.

Nümunələr

Birinci testdə zirvələri $1,2,3$ olan üçbucaqlıdır. Onun çəkisi 1 \cdot 2 \cdot 3 = 6-dır.

İkinci testdə zirvələri 1, 2, 3, 4 olan dördbucaqdır. Minimal çəki $(1,3)$ diaqonalı ilə üçbucaqlanma zamanı əldə olunur:

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

Nümunə 1

Loading

Loading

Nümunə 2

Loading

Loading