1699: Різниця сум

Бали: 35

Time limit: 2.0s

Python 3 3.0s

Memory limit: 500M

Python 3 250M

Author:

Problem type

Маємо послідовність цілих чисел \(A\) довжини \(N\), де \(A_1 = X\), \(A_{i+1} = A_i+D\) (\(1 \leq i < N\)).

Степан візьме деякі (можливо всі або жодного) з елементів у цій послідовності, а Андрій візьме всі інші.

Нехай \(S\) і \(T\) --- сума чисел, узятих Степаном та Андрієм відповідно.

Скільки існує можливих значень \(S - T\)?

Вхідний потік містить цілі числа \(N, X, D\) (\(1 \le N \le 2 \times 10^5\), \(-10^8 \le X,D \le 10^8\)).

Числа у рядку розділяються пропуском.

У вихідний потік вивести шукану кількість.

До прикладу 1:

А є (4, 6, 8). Є вісім способів взяти елементи:

((), (4, 6, 8)), ((4), (6, 8)), ((6), (4, 8) ), ((8), (4, 6))), ((4, 6), (8))), ((4, 8), (6))), ((6, 8), (4 ))) і ((4, 6, 8 ), ()).

Значення \(S - T\) у цих способах становлять -18, -10, -6, -2, 2, 6, 10 і 18, відповідно, тому існує вісім можливих значень \(S - T\).

3 4 2

2 3 -3

100 14 20

Коментарі

0

Hydra commented on Січ. 25, 2022, 3:41 після полудня

Можна дізнатися обмеження на X, N i D у цій задачі?