Задача F. Сколько треугольников?

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Рассмотрим правильный треугольник. Разделим каждую его сторону на N равных частей точками и проведём через эти точки прямые, параллельные сторонам треугольника.

Спрашивается: сколько всего треугольников на рисунке? (Учитываются треугольники разных размеров.)

Формат входного файла

Входной файл содержит единственное целое число N.

Формат выходного файла

Требуется вывести в выходной файл единственное целое число — количество треугольников.

Ограничения

1 ≤ N ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
5
2
3
13
3
28
5985

Разбор

Разобьём все треугольники на группы по горизонтальной прямой, которой принадлежит горизонтальное основание треугольника. При фиксированной горизонтальной прямой выбор третьей вершины треугольника, не лежащей на этой прямой, однозначно определяет треугольник (если, конечно, такой треугольник существует). Заметим, что треугольник получается, когда третья вершина принадлежит большому треугольнику с нижним основанием, лежащим на выбранной прямой, или треугольнику, симметричному этому треугольнику относительно выбранной прямой.

Итак, для решения задачи необходимо перебрать горизонтальные прямые и посчитать, сколько вершин принадлежат соответствующему большому треугольнику или ему симметричному.

Другой способ решения задачи

Дискуссия


0.395s 0.022s 17