Вам даны три целых числа $$$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
На бесконечной плоскости в каждой точке с целочисленными координатами записано какое-то положительное число.
Далее выбираются две базовые точки с целочисленными координатами ($$$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
В сборной команде Берляндии по футболу $$$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}.
Недавно Мише подарили новенькое взвешенное дерево, состоящее из $$$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 21 2 12 3 11 4 14 5 13 5 44 3 2
2 2
5 21 2 02 3 03 4 04 5 01 5 01 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$$$.
Петя пришел на урок информатики. На этом уроке обсуждали новую тему: геометрию. Причем не простая, а гробовая геометрия. Пете было лень решать одну из задач, которую ему дали, и как всегда, он попросил вас ему помочь.
Но в этот раз вы решили сказать, что не поможете. Петя же сказал, что если вы не поможете, то он даст вам гробовую задачу на стереометрию. А вряд ли кто захочет такое решать. Поэтому вы решили все-таки помочь с задачей на геометрию. Задача звучит так:
Дано $$$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$$$ — ответ