Твір#10452

Твір (Розбір)

Знайдемо формулу для розв'язання задачі, спираючись на кількість слів $n$ у реченні.

Нехай $n$ є парним числом. Розглянемо речення Бариша та Азіза:

Обчислимо суму чисел у масиві "різниць". Розділимо числа в масиві на дві рівні частини. Знайдемо суму чисел від $1$ до $n - 1$ n - 1 з кроком $2$ (це арифметична прогресія). У цьому діапазоні є $n /2$ чисел. Таким чином, сума всіх чисел у масиві "різниць" дорівнює:

2 \cdot \frac{1 + n - 1}{2} \cdot \frac{n}{2} = \frac{n ^{2}}{2}

2 \cdot {1 + n - 1 \over 2} \cdot {n \over 2} = {n^2 \over 2}

Нехай $n$ є непарним числом. Розглянемо речення Бариша та Азіза:

Обчислимо суму чисел у масиві "різниць". Розділимо числа в масиві на дві рівні частини. Знайдемо суму чисел від $2$ до $n - 1$ n - 1 з кроком $2$ (це арифметична прогресія). У цьому діапазоні є $(n - 1) /2$ (n - 1) / 2 чисел. Таким чином, сума всіх чисел у масиві "різниць" дорівнює:

2 \cdot \frac{2 + n - 1}{2} \cdot \frac{n - 1}{2} = \frac{( n + 1 ) \cdot ( n - 1 )}{2} = \frac{n ^{2} - 1}{2}

2 \cdot {2 + n - 1 \over 2} \cdot {n - 1 \over 2} = {(n + 1) \cdot (n - 1) \over 2} = {n^2 - 1 \over 2}

Приклад

Нехай $n = 8$ n = 8.

Сума чисел у масиві "різниць" дорівнює $8^{2} /2 = 32$ 8^2 / 2 = 32.

Нехай $n = 7$ n = 7.

Сума чисел у масиві "різниць" дорівнює $(7^{2} - 1) /2 = 24$ (7^2 - 1) / 2 = 24.

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

Зчитуємо кількість тестів $t es t s$ .

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);
}

C++

Реалізація на Python

Зчитуємо кількість тестів $t es t s$ .

tests = int(input())

for _ in range(tests):

Для кожного значення $n$ обчислюємо та виводимо результат.

  n = int(input())
  if n % 2 == 0:
    res = n * n // 2
  else:
    res = (n * n - 1) // 2
  print(res)