Олимпиада имени И.М. Дризе по информатике (программированию). Город Ижевск, 2024 год
Statement is not available in English language
A. Самое короткое условие
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны три целых числа $$$R, x, y$$$. Посчитайте количество пар целых чисел $$$(l, r)$$$ таких, что $$$1 \le l \le r \le R$$$, и таких, что среди чисел $$$l, l + 1, ..., r$$$ ровно $$$x$$$ чисел, которые делятся на $$$y$$$.

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

На ввод в единственной строке подаются три целых числа $$$R, x, y$$$ ($$$1 \le R, x, y \le 10^9$$$).

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

Выведите ответ на задачу.

Система оценки

Данная задача оценивается по группам тестов. Баллы за группу начисляются в том случае, если все необходимые подгруппы выполнены, и если все тесты данной подгруппы пройдены.

ГруппаДополнительные ограниченияБаллыНеобходимые подгруппы
$$$0$$$Примеры$$$0$$$—
$$$1$$$На отрезке $$$(1, R)$$$ существует только одно число, делящееся на y$$$10$$$—
$$$2$$$$$$R \le 5000$$$$$$25$$$—
$$$3$$$$$$R \le 10^5$$$$$$30$$$$$$2$$$
$$$4$$$Без дополнительных ограничений$$$25$$$$$$0,1,2,3$$$
Примеры
Входные данные
7 3 2
Выходные данные
4
Входные данные
17 3 3
Выходные данные
27

Statement is not available in English language
B. Найди отрицательное
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На бесконечной плоскости в каждой точке с целочисленными координатами записано какое-то положительное число.

Далее выбираются две базовые точки с целочисленными координатами ($$$x_1$$$; $$$y_1$$$) и ($$$x_2$$$; $$$y_2$$$).

Для первой базовой точки, числа, записанные в точках на расстоянии не более $$$r_1$$$, умножаются на $$$-1$$$.

Для второй базовой точки, числа, записанные в точках на расстоянии не более $$$r_2$$$, умножаются на $$$-1$$$.

Вам необходимо найти любую целочисленную точку, с координатами по модулю не превышающими $$$3*10^9$$$, в которой теперь находится отрицательное число, либо сказать, что такой точки нет.

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

В первой строке входных данных находятся три целых числа: $$$x_1$$$, $$$y_1$$$, $$$r_1$$$ ($$$1 \le x_1$$$, $$$y_1$$$, $$$r_1$$$ $$$\le 10^9$$$)

Во второй строке входных данных находятся три целых числа: $$$x_2$$$, $$$y_2$$$, $$$r_2$$$ ($$$1 \le x_2$$$, $$$y_2$$$, $$$r_2$$$ $$$\le 10^9$$$)

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

В единственной строке выведите два целых числа — координаты точки, с отрицательным значением, или -1, если такой точки нет.

Система оценки

Данная задача оценивается по группам тестов. Баллы за группу тестов начисляются только в случае прохождения всех тестов данной группы.

ГруппаДополнительные ограниченияБаллыНеобходимые подгруппы
$$$0$$$Примеры$$$0$$$—
$$$1$$$$$$x_1 = x_2$$$ и $$$y_1 = y_2$$$$$$4$$$—
$$$2$$$$$$x_1 = x_2$$$ и $$$r_1, r_2 \le 10^5$$$$$$3$$$$$$1$$$
$$$3$$$$$$x_1 = x_2$$$$$$8$$$$$$1$$$, $$$2$$$
$$$4$$$Любая точка менялась не более 1 раза$$$3$$$—
$$$5$$$Все числа не превышают $$$10^3$$$$$$25$$$$$$0$$$
$$$6$$$Все числа не превышают $$$10^6$$$$$$32$$$$$$0$$$, $$$5$$$
$$$7$$$Без дополнительных ограничений$$$25$$$$$$0,1,2,3, 4, 5, 6$$$
Примеры
Входные данные
3 3 3
7 4 2
Выходные данные
5 1
Входные данные
1 1 3
2 1 2
Выходные данные
-1 -1
Примечание
В первом тесте будет покрыта следующая область. Точка C покрыта только одной окружностью
Во втором тесте будет покрыта следующая область. Точка C покрыта только одной окружностью

Statement is not available in English language
C. Футбол в Берляндии
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В сборной команде Берляндии по футболу $$$n$$$ человек. Каждый футболист имеет майку с его порядковым номером. Майки пронумерованы таким образом, что среди номеров маек встречаются все числа от $$$1$$$ до $$$n$$$, формально говоря, номера маек образуют перестановку из $$$n$$$ чисел.

После проигрыша в чемпионате мира по футболу было принято решение о смене тренера команды. Тренер считает, что только он может быть первым номером, поэтому, он заменил майку с номером $$$1$$$ на майку с номером $$$n + 1$$$. Теперь, среди номеров маек встречаются все числа от $$$2$$$ до $$$n + 1$$$.

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

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов.

Единственная строка каждого набора входных данных содержит одно число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество игроков в сборной Берляндии по футболу.

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

Для каждого набора входных данных выведите единственное целое число — количество способов раздать игрокам новые майки.

Система оценки

Данная задача оценивается по группам тестов. Баллы за группу начисляются в том случае, если все необходимые подгруппы выполнены, и если все тесты данной подгруппы пройдены.

Пусть $$$n_i$$$ — n на i-ом наборе входных данных

ГруппаДоп. ограничениябаллыНеобходимые подгруппы
$$$t$$$$$$n_i$$$
$$$1$$$$$$t = 1$$$$$$n_i \le 10$$$$$$16$$$—
$$$2$$$—$$$n_i \le 10$$$$$$9$$$1
$$$3$$$—$$$\sum n_i \le 10^3$$$$$$29$$$1
$$$4$$$—$$$ n_i \le 10^3$$$$$$11$$$$$$1$$$, $$$2$$$, $$$3$$$
$$$5$$$$$$t = 1$$$—$$$21$$$$$$1$$$
$$$6$$$——$$$14$$$$$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$
Пример
Входные данные
2
1
3
Выходные данные
1
2
Примечание

В первом наборе входных данных изначальная последовательность: {1}. После смены тренера: {2}. Можно сопоставить единственным образом

Во втором наборе входных данных изначальная последовательность: {1, 2, 3}. После смены тренера: {2, 3, 4}. Можно сопоставить двумя способами: {2, 4, 3} и {4, 2, 3}.

Statement is not available in English language
D. Посчитай-ка пути
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Мише подарили новенькое взвешенное дерево, состоящее из $$$n$$$ вершин и $$$n - 1$$$ ребра. Его друг Саша узнал о новом подарке и решил позадавать ему $$$q$$$ вопросов, связанных с этим деревом. Миша был не силен в деревьях, и поэтому попросил вас ответить на эти $$$q$$$ вопросов, которые представляют из себя следующее:

Каждый вопрос состоит из двух вершин $$$u$$$ и $$$v$$$ ($$$u \neq v$$$), а так же из целого числа $$$d$$$. Выпишем все веса ребер на простом пути от вершины $$$u$$$ до $$$v$$$ (очевидно, что такой путь всегда один): $$${w_1, w_2, ..., w_k}$$$. Необходимо посчитать количество таких индексов $$$i$$$ ($$$0 \le i \le k - 1$$$), что $$$(w_1 + w_2 +...+ w_i) * (w_{i + 1} + w_{i + 2} +...+ w_k) = d$$$.

Будем считать, что при $$$i = 0$$$, мы будем проверять на истину $$$(w_{1} + w_{2} +...+ w_k) = d$$$.

Помогите Мише с этими сложными вопросами.

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

На ввод в первой строке вводится число $$$n$$$ и $$$q$$$ ($$$2 \le n, q \le 10^5$$$) — число вершин в дереве и количество вопросов.

Затем следуют $$$n - 1$$$ строк, каждая из которых содержит три числа $$$u_i$$$, $$$v_i$$$ и $$$k_i$$$, описывающих ребро $$$i$$$ ($$$1 \le u_i, v_i \le n, u_i \neq v_i, |k_i| \le 1000$$$) — $$$u_i$$$ и $$$v_i$$$ - вершины, соединяемые ребром, и $$$k_i$$$ - значение, записанное на данном ребре (номера ребер $$$i$$$ нумеруются от $$$2$$$ до $$$n$$$).

Затем следует $$$q$$$ вопросов Саши, описывающихся тремя числами $$$u_j$$$, $$$v_j$$$ и $$$d_j$$$ ($$$1 \le u_j, v_j \le n, u_j \neq v_j, |d_j| \le 10^{16}$$$).

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

В единственной строке выведите $$$q$$$ чисел — ответы на вопросы.

Система оценки

Данная задача оценивается по группам тестов. Баллы за группу начисляются в том случае, если все необходимые подгруппы выполнены, и если все тесты данной подгруппы пройдены.

ГруппаДополнительные ограниченияБаллыНеобходимые подгруппы
$$$0$$$Примеры$$$0$$$—
$$$1$$$$$$n, q \le 1000$$$$$$15$$$$$$0$$$
$$$2$$$Граф представляет из себя полное бинарное дерево*$$$15$$$—
$$$3$$$для всех ребер $$$k_i = 1$$$$$$20$$$—
$$$4$$$Без дополнительных ограничений$$$50$$$$$$0,1,2,3$$$

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

Примеры
Входные данные
5 2
1 2 1
2 3 1
1 4 1
4 5 1
3 5 4
4 3 2
Выходные данные
2
2
Входные данные
5 2
1 2 0
2 3 0
3 4 0
4 5 0
1 5 0
1 3 0
Выходные данные
4
2
Примечание
Графы из первого и второго примеров

В первом примере, если мы выпишем веса ребер по ходу движения из вершины $$$3$$$ в $$$5$$$, то будет: {$$$1, 1, 1, 1$$$}. Два способа разбить путь так, чтобы произведение было $$$4$$$: {$$$1, 1$$$} и {$$$1, 1$$$}, $$$(1 + 1) * (1 + 1) = 4$$$; и {$$$1, 1, 1, 1$$$}, $$$(1 + 1 + 1 + 1) = 4$$$. Аналогично можно сделать и для второго вопроса в первом примере, и мы получим $$$2$$$.

Statement is not available in English language
E. Гробовая геометрия
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Дано $$$n$$$ целочисленных точек на плоскости, где $$$i$$$-ая точка имеет вид $$$(x_i, y_i)$$$. Также загадана одна дополнительная точка, пусть она имеет вид $$$(a, b)$$$. Дополнительно, вам дан массив $$$d$$$ размера $$$n$$$, который представляет из себя перемешанный список целочисленных квадратов расстояний от точки $$$(a, b)$$$ до всех точек $$$(x_i, y_i)$$$ для $$$1 \le i \le n$$$. То есть, каждому элементу списка $$$d$$$ мы можем сопоставить точку $$$(x_i, y_i)$$$ из списка изначальных точек, причем данный элемент будет равен квадрату расстояния между этой точкой и $$$(a, b)$$$, и каждая точка сопоставляется ровно одному элементу списка $$$d$$$.

Вам необходимо по всем данным восстановить любую такую целочисленную точку $$$(a, b)$$$, для которой выполняется условие $$$-5 \cdot 10^8 \le a, b \le 5 \cdot 10^8$$$. Причем сделать это надо для $$$t$$$ наборов, потому что одноклассники Пети попросили вас тоже решить задачу.

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

На ввод в первой строке подается число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество тестов.

В каждом тесте в первой строке вводится число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество точек на плоскости.

Затем в каждом тесте в следующих $$$n$$$ строках вводятся точки на плоскости $$$x_i, y_i$$$ ($$$|x|, |y| \le 5 \cdot 10^8$$$) — координаты $$$i$$$-ой точки.

И в $$$n + 2$$$-ой строке вводится массив целых чисел $$$d$$$ ($$$0 \le d_i \le 2 \cdot 10^{18}$$$).

Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$10^5$$$. Также гарантируется, что во всех тестах, за исключением примера, точки сгенерированы равновероятно.

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

Для каждого теста выведите подходящую целочисленную точку $$$(a, b)$$$, для которой выполняется условие $$$-5 \cdot 10^8 \le a, b \le 5 \cdot 10^8$$$. Если ответов существует несколько, то выведите любой. Гарантируется, что ответ существует.

Система оценки

В данной задаче $$$50$$$ тестов, каждый из которых оценивается в $$$2$$$ балла. Гарантируется, что существуют $$$10$$$ тестов, где для всех точек $$$|x|, |y| \le 10$$$, $$$t \le 100$$$ (существует ответ $$$(a, b)$$$ такой, что $$$-10 \le a, b \le 10$$$), а также существуют другие $$$20$$$ тестов, где сумма $$$n$$$ во всем тестам до $$$100$$$. Все тесты оцениваются независимо.

В этих $$$10$$$ тестах точки генерируются равновероятно в диапазоне $$$(-10, 10)$$$, в остальных — в диапазоне $$$(-5 \cdot 10^8, 5 \cdot 10^8)$$$.

Пример
Входные данные
1
4
5 1
-1 5
1 1
4 6
10 8 8 20
Выходные данные
3 3
Примечание
Иллюстрация к примеру. Точка $$$A$$$ — ответ