eolymp
Yarışlar

Комбинаторика. Формула

Минимальная триангуляция

Вам задан правильный многоугольник из n вершин, пронумерованных от 1 до n против часовой стрелки. Триангуляция данного многоугольника - это набор треугольников такой, что каждая вершина любого из треугольников является вершиной первоначального многоугольника, не существует пары треугольников имеющих положительную площадь пересечения, и площадь объединения треугольников равна площади многоугольника. Вес триангуляции — это сумма весов треугольников из которых она состоит, где весом треугольника является произведение меток его вершин.

Найдите минимальный вес среди всех триангуляций заданного многоугольника.

Входные данные

Одно целое число n (3n500) - количество вершин в правильном многоугольнике.

Выходные данные

Выведите минимальный вес среди всех триангуляций заданного многоугольника.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
Çıxış verilənləri #1
6
Giriş verilənləri #2
4
Çıxış verilənləri #2
18