В правильном n-угольнике (n чётное) проведены диагонали так, как показано на рисунке. Определите количество областей, на которое разбивается фигура.
Формат входных данных
Единственная строка входных данных содержит натуральное чётное число n.
Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Выведите одно натуральное число — ответ на вопрос задачи.
Ограничения
4 ≤ n ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 105, получат не менее 40 баллов.
Сегодня Аля на занятии кружка по математике узнала, что такое факториал. В качестве учебного проекта она выбрала разбор и решение следующей задачи: "Определить последнюю ненулевую цифру факториала данного числа n". Да вот только не получается у неё что-то. Помогите Але!
Формат входных данных
Единственная строка входного файла содержит натуральное число n.
Формат выходных данных
Выведите одну десятичную цифру — ответ на вопрос задачи.
Ограничения
1 ≤ n ≤ 105
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 18, получат не менее 20 баллов.
Пояснение к примеру
В примере дано n = 10. Факториал числа 10 равен 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 = 3628800. Последняя ненулевая цифра 8.
Тимофей отметил на координатной плоскости все точки (x, y) с натуральными координатами, для которых выполняется условие "x делится на y". Потом он, начиная с точки (1, 1), соединил эти точки отрезками, если они были соседними по стороне или диагонали единичного квадрата. Те точки, до которых он смог добраться, мальчик назвал достижимыми.
Определите достижимость указанной точки.
Формат входных данных
Две строки входных данных содержат два натуральных числа x и y.
Назовём прямоугольник почти квадратом, если его соседние стороны отличаются на 1. Определите наименьшее количество разрезов, после которых данный прямоугольник окажется разбит на почти квадраты.
Для определённости считайте, что после каждого разреза от прямоугольника должен отделяться хотя бы один почти квадрат.
Формат входных данных
Две строки входных данных содержат два натуральных числа a и b — размеры прямоугольника.
Формат выходных данных
Выведите одно неотрицательное целое число — ответ на вопрос задачи. Если сделать требуемые разрезы невозможно, выведите число -1.
Ограничения
1 ≤ a, b ≤ 200
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примерам
В первом примере прямоугольник размером 1 × 3 возможно разрезать только на части 1 × 2 и 1 × 1. Вторая из этих частей не является почти квадратом, а разрезать её на ещё более мелкие части невозможно.
Во втором примере прямоугольник размером 4 × 3 уже является почти квадратом, разрезать его не нужно.
В третьем примере от прямоугольника размером 4 × 4 первым разрезом можно отделить почти квадрат4 × 3, а часть 4 × 1 вторым разрезом поделить пополам, получив два почти квадрата2 × 1.
