Прямые
Рассмотрим положительное целое N. Пусть A, B и C – такие неотрицательные целые числа, что A+B+C=N. Пусть на координатной оси отмечено N точек с одинаковым интервалом между каждыми двумя соседними. Проведите прямые под углом 45 градусов к координатной оси через A левых точек, проведите прямые под углом 90 градусов к координатной оси через B следующих точек и под углом 135 градусов к координатной оси – через оставшиеся C точек. Эти прямые пересекутся в некотором количестве точек.
Для ясности смотрите рисунок, где указан случай N=5, A=1, B=2, C=2. Всего получилось 6 точек пересечения.
Ваша задача довольно проста – для заданного N посчитать сумму количеств точек пересечения для всех возможных троек A, B, C.
Технические условия
Входные данные
Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 1000).
Каждая из следующих T строк содержит число N (2 ≤ N ≤ 106) – количество точек на прямой в данном тесте.
Выходные данные
Выведите T строк вида “Case #A: B”, где A – номер теста (начиная с 1), B – сумма количеств точек пересечения для заданного N.
Информация о задаче
Лимит времени: 10 секундЛимит памяти: 64 MB
Баллы за пройденный тест: 10
Сложность: 63% 3/8
Пример
Пример входных данных3 2 3 5 |
Пример выходных данныхCase #1: 3 Case #2: 13 Case #3: 91 |
| ← Длиннейшая цепочка | Список задач | Доминация по Парето → |