#3015

Домино

Темы: [Арифметические алгоритмы]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Москва, 2010, Задача B ]

Рассмотрим N-домино. В таком домино каждая костяшка состоит из двух половинок, на каждой из которых нарисовано от 0 до N точек. Полный комплект костяшек такого домино содержит все возможные костяшки, каждую — по одному разу. Например, для N=2 в комплект войдут следующие костяшки: (0,0), (0,1), (0,2), (1,1), (1,2) и (2,2)

Напишите программу, которая по заданному N определит, сколько всего точек изображено на всех костяшках полного комплекта N-домино.

Входные данные

Вводится натуральное число N (1<=N<=30).

Выходные данные

Программа должна напечатать одно число - общее количество точек на всех костяшках полного комплекта N-домино.

Примеры

Входные данные

Выходные данные

#3140

Феодальные отношения

Темы: ["Длинная" арифметика]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Московская областная олимпиада, 2008, Задача B ]

Во Флатландии с некоторых пор процветают феодальные отношения – у каждого порядочного феодала есть ровно два вассала, у непорядочных – вассалов нет совсем. Каждый феодал строит свой замок в городе на прямой, при этом:

высота замка (всегда целое положительное число) должна быть строго больше высот замков его вассалов (для соблюдения субординации).
замки первого из двух вассалов и всех вассалов этого вассала должны быть построены слева, второго вассала и его вассалов – справа (для пресечения междоусобиц). Это правило должно выполняться для всех
высота замка должна быть минимально возможной (для экономии ресурсов)
число всех подчиненных (непосредственно или через промежуточных) у правого и левого вассалов одинаково (для баланса сил).

Для удобства замки феодалов занумерованы натуральными числами по порядку слева направо, начиная с единицы, и разбиты на улицы. Улица (i, j) представляет собой последовательность подряд идущих замков, начиная с замка под номером i и заканчивая замком с номером j (i ≤ j)

Однажды в город приехал новый феодал и пожелал выкупить там замок у одного из жителей. Также ему стало интересно узнать социальный статус соседей по улице, однако, город к тому времени так разросся, что феодал уже не мог сделать этого самостоятельно. Напишите программу, которая поможет ему!

Входные данные

Первая строка входного файла содержит число N (1 ≤ N ≤ 30000) — высота замка единственного главного феодала в городе, который никому не подчиняется. Далее, в следующих двух строках идут числа i и j ($0 \leq i, j < 10^{10000}$), задающие улицу (i, j), на которой хочет приобрести замок новый феодал (гарантируется, что замки с номерами i и j находятся в черте города, i ≤ j, j – i ≤ 10⁵).

В выходной файл требуется вывести высоты всех замков на указанной улице слева направо через пробел.

Примечание

Будут оцениваться и частичные решения задачи при малых N. Частичные решения для N<20 набирают до 40 баллов, а для N<50 набирают не более 70 баллов.

Ввод	Вывод
2 1 3	1 2 1
3 3 7	1 3 1 2 1
50 128873293 128873293	1

#3182

Колесо Фортуны

Темы: [Линейный поиск] [Остатки]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 1 день, Задача B ]

Развлекательный телеканал транслирует шоу «Колесо Фортуны». В процессе игры участники шоу крутят большое колесо, разделенное на сектора. В каждом секторе этого колеса записано число. После того как колесо останавливается, специальная стрелка указывает на один из секторов. Число в этом секторе определяет выигрыш игрока.

Юный участник шоу заметил, что колесо в процессе вращения замедляется из-за того, что стрелка задевает за выступы на колесе, находящиеся между секторами. Если колесо вращается с угловой скоростью $v$ градусов в секунду, и стрелка, переходя из сектора $X$ к следующему сектору, задевает за очередной выступ, то текущая угловая скорость движения колеса уменьшается на $k$ градусов в секунду. При этом если $v \le k$, то колесо не может преодолеть препятствие и останавливается. Стрелка в этом случае будет указывать на сектор $X$.

Юный участник шоу собирается вращать колесо. Зная порядок секторов на колесе, он хочет заставить колесо вращаться с такой начальной скоростью, чтобы после остановки колеса стрелка указала на как можно большее число. Колесо можно вращать в любом направлении и придавать ему начальную угловую скорость от $a$ до $b$ градусов в секунду.

Требуется написать программу, которая по заданному расположению чисел в секторах, минимальной и максимальной начальной угловой скорости вращения колеса и величине замедления колеса при переходе через границу секторов вычисляет максимальный выигрыш.

Входные данные

Первая строка входного файла содержит целое число $n$ — количество секторов колеса ($3 \le n \le 100$).

Вторая строка входного файла содержит $n$ положительных целых чисел, каждое из которых не превышает $1000$ — числа, записанные в секторах колеса. Числа приведены в порядке следования секторов по часовой стрелке. Изначально стрелка указывает на первое число.

Третья строка содержит три целых числа: $a$, $b$ и $k$ ($1 \le a \le b \le 10^9$, $1 \le k \le 10^9$).

Выходные данные

В выходном файле должно содержаться одно целое число — максимальный выигрыш.

Примечание

В первом примере возможны следующие варианты: можно придать начальную скорость колесу равную 3 или 4, что приведет к тому, что стрелка преодолеет одну границу между секторами, или придать начальную скорость равную 5, что позволит стрелке преодолеть 2 границы между секторами. В первом варианте, если закрутить колесо в одну сторону, то выигрыш получится равным 2, а если закрутить его в противоположную сторону, то — 5. Во втором варианте, если закрутить колесо в одну сторону, то выигрыш будет равным 3, а если в другую сторону, то — 4.

Во втором примере возможна только одна начальная скорость вращения колеса — 15 градусов в секунду. В этом случае при вращении колеса стрелка преодолеет семь границ между секторами. Тогда если его закрутить в одном направлении, то выигрыш составит 4, а если в противоположном направлении, то — 3.

Наконец, в третьем примере оптимальная начальная скорость вращения колеса равна 2 градусам в секунду. В этом случае стрелка вообще не сможет преодолеть границу между секторами, и выигрыш будет равен 5.

Правильные решения для тестов, в которых $1 \le a \le b \le 1000$, будут оцениваться из 50 баллов.

Примеры

Входные данные

5
1 2 3 4 5
3 5 2

Выходные данные

Входные данные

5
1 2 3 4 5
15 15 2

Выходные данные

Входные данные

5
5 4 3 2 1
2 5 2

Выходные данные

#3208

Делители

Темы: [НОД и алгоритм Евклида] [Перебор с отсечением]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 2 день, Задача C ]

Натуральное число $a$ называется делителем натурального числа $b$, если $b = ac$ для некоторого натурального числа $c$. Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 — нет.

Будем называть нормальным набор из $k$ чисел ($a_1, a_2, \ldots, a_k$), если выполнены следующие условия:

каждое из чисел $a_i$ является делителем числа $n$;
выполняется неравенство $a_1 \lt a_2 \lt \ldots \lt a_k$;
числа $a_i$ и $a_{i+1}$ для всех $i$ от $1$ до $k - 1$ являются взаимно простыми;
произведение $a_1a_2\ldots a_k$ не превышает $n$.

Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.

Требуется написать программу, которая по заданным значениям $n$ и $k$ определяет количество нормальных наборов из $k$ делителей числа $n$.

Входные данные

Первая строка входного файла содержит два целых числа: $n$ и $k$ ($2 \le n \le 10^8$, $2 \le k \le 10$).

Выходные данные

В выходном файле должно содержаться одно число — количество нормальных наборов из $k$ делителей числа $n$.

Примечание

Правильные решения для тестов, в которых $n \le 1000$ и $k = 2$, оцениваются из 30 баллов.

Правильные решения для тестов, в которых $k = 2$, оцениваются из 60 баллов (в эти баллы включаются также 30 баллов для случая $n \le 1000$, $k = 2$).

Примеры

Входные данные

90 3

Выходные данные

Входные данные

10 2

Выходные данные

#3787

Кривая дракона

Темы: [Арифметические алгоритмы] [Цикл for]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2011, Задача B ]

Сегодня мальчик Саша на уроке математики узнал про фракталы. Учитель показывал так называемую «кривую дракона». Она представляет собой геометрическую фигуру, которая строится следующим образом: на первом шаге проводится отрезок из начала координатной плоскости в точку (0; 1). Далее на каждом шаге из конца фрактала повторяется уже нарисованная часть фигуры, повернутая на 90 градусов против часовой стрелки (см. рисунок).

После уроков Саша попробовал сам изобразить «кривую дракона», и теперь он хочет знать, в какой точке координатной плоскости он закончил рисовать фрактал, проделав описанные выше N шагов. Требуется написать программу, которая по заданному числу N определяет координаты конца фрактала после выполнения N шагов.

$\text{[math]}$

Входные данные

Вводится одно целое число N (1 ≤ N ≤ 30).

Выходные данные

Выведите два числа через пробел — координаты конца фрактала.

Примеры

Входные данные

Выходные данные

1 1

Входные данные

Выходные данные

2 -2