Задача 1. Кодовый замок ≡

Условие

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

В один из дней отдыха во время того, как Влад был на море, на работе случилась беда, и Владу срочно пришлось вернуться в гостиницу. Но главная проблема ждала его в номере: ему был нужен ноутбук, но он не помнил пароль, который он выбрал. Он лишь помнил то, что выбранное им число кратно a, b и c. По этим данным, определите, какое минимальное количество вариантов пароля от сейфа придется перебрать Владу, чтобы он точно нашел верный.

Формат входных данных

На вход подаются целые числа n, a, b и c.

Формат выходных данных

Выведите одно число - минимальное количество вариантов, которые нужно перебрать, чтобы гарантированно найти верный.

Ограничения

1 ≤ n ≤ 10⁹

1 ≤ a, b, c ≤ 100

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 10⁵ получат не более 60 баллов.

Пояснение к примеру

В примере Владу, чтобы гарантированно найти пароль, необходимо перебрать следующие варианты: 28, 56 и 84.

Примеры тестов

100 2 4 7

3

Задача 2. Атака на боссов ≡

Условие

Вот он, момент истины! Мальчик Вова дошел в своей любимой игре до самого последнего уровня. На нем ему осталось последовательно победить n боссов. Сначала он должен победить босса под номером 1, затем под номером 2, затем 3, и так до номера n. Каждый босс имеет силу a_i. Для того, чтобы гарантированно победить босса, сила персонажа Вовы на данном шаге должна быть строго больше силы босса. Если Вова побеждает босса, то его сила увеличивается на силу побежденного босса.

Силы персонажа Вовы хватало на то, чтобы победить всех боссов, поэтому перед последним уровнем он решил передохнуть. Но проблема пришла откуда не ждали! На серверах игры произошел сбой, и у всех персонажей в игре обнулились силы. Вова очень расстроился этому, ведь он долго и упорно набирал силу, проходя все уровни. Сейчас ему придется по новой проходить уровни, чтобы набрать нужную силу. Но Вова не хочет проходить все уровни, поэтому он просит Вас написать программу, которая определит, какое минимальное количество силы Вове нужно набрать, чтобы гарантированно победить всех боссов.

Формат входных данных

В первой строке записано целое число n - количество боссов.

Во второй строке записано n целых чисел a_i - силы боссов.

Формат выходных данных

Выведите одно целое число - минимальное необходимое количество силы, чтобы победить всех боссов.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ a_i ≤ 10⁹

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

5
2 5 8 4 6

4

Задача 3. Работа в парах ≡

Условие

Учитель по информатике Виктор считается лучшим в крае из-за своих подходов к обучению. Один из его подходов преподавания - работа детей в парах после пройденной темы.

В классе Виктора учится n детей. Сегодня он на уроке с ними прошел новую тему: графы, теперь настало время практики. Он решил сформировать пары учеников, которые будут работать вместе. Формирует пары он по следующему принципу: в каждой паре учеников знания должны различаться не более, чем на k единиц. Делает он это для того, чтобы ученики работали максимально продуктивно. Эту величину k он вычислил экспериментальным путем. Если для какого-то ученика не получается сформировать пару, то наиболее продуктивно он будет работать один. Для каждого ученика он определил уровень знаний: ученик с номером i имеет уровень знаний, равный a_i. Он решил выбрать q учеников и узнать, какое количество учеников подойдут к ним в пару. Он просит Вас написать программу, которая для каждого выбранного ученика будет определять количество учеников, с которым он сможет организовать пару.

Формат входных данных

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

Во второй строке через пробел записано n целых чисел a_i - уровни знаний учеников.

В третьей строке записано целое число q - количество выбранных учеников.

В четвертой строке записано q целых чисел b_j - номера выбранных учеников.

Формат выходных данных

Программа должна вывести q целых чисел - количество учеников, с которыми Виктор может организовать пару для ученика b_j.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ k, a_i ≤ 10⁹

1 ≤ q, b_i ≤ n

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

5 2
6 9 7 3 8
3
3 4 2

3 0 2

Задача 4. Неисправный робот ≡

Условие

Программист Влад увлекается не только программированием, но и робототехникой. На днях ему пришла идея создать робота, который будет ездить по городу со скоростью 1 метр в секунду и замерять расстояние над уровнем моря через каждую секунду. При старте робот делает первый замер расстояния над уровнем моря. Робот едет сначала некоторое расстояние в одну сторону, потом разворачивается на 180 градусов и едет обратно до точки старта. Робот выполняет разворот 1 секунду. После разворота робот продолжает замерять данные.

Когда робот вернулся к Владу, он заметил, что данные перемешались, и теперь у него данные о движении в обе стороны находятся в одном массиве длиной n. Но это не единственная проблема: датчик оказался бракованным и некоторые показания в этом массиве являются ложными. Но так как робот ездил в обе стороны, то некоторые данные в массиве данных равные. Поэтому он решил выяснить, какое максимальное возможное время в секундах робот мог ездить. Он просит Вас написать программу, которая поможет ему это выяснить.

Формат входных данных

В первой строке записано целое число n - длина массива данных.

Во второй строке записано n целых чисел a_i - показания датчика.

Формат выходных данных

Выведите одно целое число - максимальное время в секундах, которое робот мог проехать.

Ограничения

4 ≤ n ≤ 2000

1 ≤ a_i ≤ 100

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснение к примеру

В примере, робот при старте сделал замер 2 метра. Затем робот, проехав первую секунду, сделал замер 4. Далее робот делает разворот 1 секунду, после делает замер 4. Спустя следующую секунду робот возвращается в стартовую точку, делая контрольный замер в 2 метра. Итого робот проехал 3 секунды.

Примеры тестов

6
2 3 4 5 4 2

3

Задача 5. Оптимальное удаление ≡

Условие

Дано дерево, состоящее из n вершин. Корнем дерева считается вершина под номером 1. Необходимо удалить одно ребро из дерева (образовав тем самым еще одно дерево с новым корнем) так, чтобы сумма расстояний от корня до всех вершин была минимально возможной. Напишите программу, которая определит эту сумму.

Формат входных данных

В первой строке записано целое число n - количество вершин в дереве.

В следующих n − 1 строках записано по два различных целых числа a_i и b_i - вершины дерева, которые соединены между собой.

Формат выходных данных

Выведите одно целое число - минимально возможную сумму расстояний от корня до всех вершин.

Ограничения

2 ≤ n ≤ 10⁵

1 ≤ a_i, b_i ≤ n

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснение к примеру

Минимальную сумму расстояний от корня до всех вершин можно получить, удалив ребро между вершинами 4 и 9. Тогда сумма расстояний от корня до всех вершин первого дерева будет 14, а второго (с корнем в вершине 9) 1.

Примеры тестов

10
1 2
1 3
2 4
2 5
3 6
4 9
6 7
6 8
9 10

15