Задача F. Сколько треугольников? ≡
| Автор: | Г. Гренкин | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt |
Условие
Рассмотрим правильный треугольник. Разделим каждую его сторону на N равных частей точками и проведём
через эти точки прямые, параллельные сторонам треугольника.
Спрашивается: сколько всего треугольников на рисунке? (Учитываются треугольники разных размеров.)
Формат входного файла
Входной файл содержит единственное целое число N.
Формат выходного файла
Требуется вывести в выходной файл единственное целое число — количество треугольников.
Ограничения
1 ≤ N ≤ 1000
Примеры тестов
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|
Разбор
Разобьём все треугольники на группы по горизонтальной прямой, которой принадлежит горизонтальное основание треугольника. При фиксированной горизонтальной прямой выбор третьей вершины треугольника, не лежащей на этой прямой, однозначно определяет треугольник (если, конечно, такой треугольник существует). Заметим, что треугольник получается, когда третья вершина принадлежит большому треугольнику с нижним основанием, лежащим на выбранной прямой, или треугольнику, симметричному этому треугольнику относительно выбранной прямой.
Итак, для решения задачи необходимо перебрать горизонтальные прямые и посчитать, сколько вершин принадлежат соответствующему большому треугольнику или ему симметричному.