printРабочее место участника

printЗадачи

2209. Кольцевая линия

Ограничения: время – 1s/2s, память – 256MiB Ввод: circle.in или стандартный ввод Вывод: circle.out или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В городе, в котором живут друзья Андрей и Борис, метро состоит из единственной кольцевой линии, вдоль которой на равном расстоянии друг от друга расположены `n` станций, пронумерованных от 1 до `n`. Участок линии метро между двумя соседними станциями называется перегоном.
Поезда по кольцевой линии двигаются как по часовой стрелке, так и против часовой стрелки, поэтому чтобы добраться от одной станции до другой, пассажир может выбрать то направление, в котором требуется проехать меньше перегонов. Минимальное число перегонов, которое необходимо проехать, чтобы добраться от одной станции до другой, назовем расстоянием между станциями.
Друзья заметили, что выполняется следующее условие: если загадать некоторую станцию `X` и выписать для нее два числа: `D_a` – расстояние от станции, на которой живет Андрей, до станции `X` и `D_b` – расстояние от станции, на которой живет Борис, до станции `X`, то полученная пара чисел `[D_a,\ D_b]` будет однозначно задавать станцию `X`.
Например, если `n\ =\ 4`, Андрей живет на станции 1, а Борис живет на станции 2, то станция 1 задается парой `[0,\ 1]`, станция 2 – парой `[1,\ 0]`, станция 3 – парой `[2,\ 1]` и станция 4 – парой `[1,\ 2]`.
Их одноклассник Сергей живет в соседнем городе и не знает, на каких станциях живут Андрей и Борис. Чтобы найти друзей, он заинтересовался, сколько существует вариантов пар станций `A,\ B`, таких что если Андрей живет на станции `A`, а Борис – на станции `B`, то выполняется описанное выше условие.
Требуется написать программу, которая по числу станций `n` на кольцевой линии определяет искомое количество вариантов.
Формат входного файла
Первая строка входного файла содержит одно целое число `n` (`3 ≤ n ≤ 40 000`).
Формат выходного файла
Выходной файл должен содержать одно число - искомое количество вариантов.

Пример ввода 1

4

Пример вывода 1

8

Пример ввода 2

5

Пример вывода 2

20
Пояснения к примеру
В первом примере подходят следующие варианты:
Андрей живет на станции 1, а Борис на станции 2;
Андрей живет на станции 1, а Борис на станции 4;
Андрей живет на станции 2, а Борис на станции 1;
Андрей живет на станции 2, а Борис на станции 3;
Андрей живет на станции 3, а Борис на станции 2;
Андрей живет на станции 3, а Борис на станции 4;
Андрей живет на станции 4, а Борис на станции 1;
Андрей живет на станции 4, а Борис на станции 3.
Система оценки и описание подзадач
В этой задаче три подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи успешно пройдены.
Подзадача 1 (25 баллов)
`3 ≤ n ≤ 50`.
Подзадача 2 (25 баллов)
`3 ≤ n ≤ 500`.
Подзадача 3 (50 баллов)
`3 ≤ n ≤ 40\ 000`.
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Источник: региональный этап Всероссийской олимпиады по информатике 2014/2015, http://neerc.ifmo.ru/school/
loading