10452. Сочинение

В школе Азизу задали написать сочинение. Срок сдачи приближается, а Азиз до сих пор ничего не написал. Но он знает, что его друг Барыш в прошлом году уже выполнял это же задание и Азиз решил этим воспользоваться. Однако, Азиз не хочет, чтобы система обнаружения плагиатов смогла это выявить. Поэтому, Азиз решает написать слова во всех предложениях сочинения Барыша в обратном порядке. После этого Азиз считает разницу между исходным предложением и предложением, которое у него получилось.

Сочинение Барыша состоит из t предложений. Каждое предложение состоит из уникальных слов.

Если количество слов в предложении обозначить числом n, то само предложение можно обозначить последовательностью {1, 2, …, n}. Тогда предложение соответствующее сочинению Азиза будет обозначаться последовательностью {n, n – 1, …, 1}.

Разница между исходным предложением и предложением Азиза считается как сумма абсолютных значений разниц между позициями, где встречается слово в предложении Барыша и где встречается то же самое слово в предложении Азиза, для всех слов этих предложений. Например, в предложении, состоящем из 3-х слов, если обозначить предложение Барыша как {1, 2, 3}, то предложение Азиза будет {3, 2, 1} и разница между предложениями будет |1 − 3| + |2 − 2| + |3 − 1| = 4.

Вход. В первой строке дается одно целое число t (1 ≤ t ≤ 10⁵) – количество предложений в сочинении Барыша. В каждой из последующих t строк находится одно число n_i (1 ≤ n_i ≤ 10⁹) – количество слов в i-ом предложении.

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

Пример входа	Пример выхода
3 4 3 7	8 4 24

РЕШЕНИЕ

математика

Анализ алгоритма

Найдем формулу – ответ на задачу в зависимости от значения количества слов n в предложении.

Пусть n четное. Раcсмотрим предложения Барыша и Азиза:

Вычислим сумму чисел в массиве “разница”. Числа в массиве разобьем на две части (одинаковые). Найдем сумму чисел от 1 до n – 1 с шагом 2 (арифметическая прогрессия). Всего имеется n / 2 чисел на этом интервале. Следовательно сумма всех чисел в массиве “разница” равна

=

Пусть n нечетное. Расcмотрим предложения Барыша и Азиза:

Вычислим сумму чисел в массиве “разница”. Числа в массиве разобьем на две части (одинаковые). Найдем сумму чисел от 2 до n – 1 с шагом 2 (арифметическая прогрессия). Всего имеется (n – 1) / 2 чисел на этом интервале. Следовательно сумма всех чисел в массиве “разница” равна

= =

Пример

Пусть n = 8.

Cумма чисел в массиве “разница” равна 8² / 2 = 32.

Пусть n = 7.

Cумма чисел в массиве “разница” равна (7² – 1) / 2 = 24.

Реализация алгоритма

Читаем количенство тестов tests.

scanf("%d", &tests);

while (tests--)

{

Для каждого значения n вычисляем и выводим ответ.

scanf("%d", &n);

if (n % 2 == 0)

res = n * n / 2;

else

res = (n * n - 1) / 2;

printf("%lld\n", res);

}