Вам нужно посчитать количество забавных чисел на промежутке от $$$l$$$ до $$$r$$$ включительно. Число называется забавным, если сумма обостренности цифр из которых он состоит равно самому числу. Значение обостренности цифры $$$x$$$ равно $$$x^x$$$. Например сумма обостренности цифр числа $$$3153$$$ равна $$$3^3 + 1^1 + 5^5 + 3^3$$$ = $$$3180$$$.
В единственной строке дается $$$l$$$, $$$r$$$ $$$(1 \le l \le r \le 10^9)$$$, задающий промежуток.
Вывести в единственной строке число равное количеству забавных чисел на промежутке.
2020 4040
1
Абай играет в довольно странную игру, где ягоды могут поедать друг-друга (wat??? $$$\odot _\bigcirc \odot$$$). В кругу расположено $$$N$$$ ягод, которые пронумерованы от 1 до $$$N$$$. У каждой ягоды с номером $$$i$$$ есть две соседние ягоды с номерами $$$i - 1$$$ и $$$i + 1$$$. Ягоды с номерами 1 и $$$N$$$ также являются соседями друг-другу. Также у каждой ягоды есть вес, у $$$i$$$-й ягоды он равен $$$W_i$$$. За один ход разрешается выбрать две соседние ягоды, пусть их вес равен $$$x$$$ и $$$y$$$ ($$$x \gt y$$$), тогда, если $$$x - y = 1$$$, то ягода с весом $$$x$$$ съедает ягоду с весом $$$y$$$, при этом ее вес по-прежнему остается равен $$$x$$$. После хода съеденная ягода исчезает и все ягоды сдвигаются друг другу так, что у каждой ягоды по-прежнему есть 2 соседа. Например, пусть в кругу стояли ягоды 2, 4, 3, 5, 1, 6 (2 и 6 — соседи). Если 4 съедает 3, круг станет таким: 2, 4, 5, 1, 6. То есть у 4 новый сосед — 5. Уровень считается пройденным, если остается только 1 ягода. Помогите Абаю узнать, возможно ли пройти уровень.
В первой строке вводится натуральное число $$$N$$$ — количество ягод. ($$$1 \leq N \leq 2 \times 10^5$$$).
На следующей строке вводятся $$$N$$$ чисел — веса ягод в порядке обхода по кругу. Гарантируется, что все веса ягод различны, а также являются целыми числами от 1 до $$$N$$$.
Выведите YES, если возможно пройти уровень, иначе NO.
3 1 3 2
YES
4 4 1 3 2
NO
Однажды Абаю приснилось, как он был мэром города. В один из дней на главном проспекте Абая случилась проблема — некоторые светофоры сломались. Всего на проспекте есть $$$N$$$ перекрестков, пронумерованных от $$$1$$$ до $$$N$$$ от начала до конца проспекта. На каждом перекрестке есть по одному светофору. Абаю необходимо починить все сломанные светофоры, для этого существует $$$M$$$ бригад, $$$i$$$-я бригада чинит все светофоры с номерами от $$$L_i$$$ до $$$R_i$$$ включительно. Разрешается чинить один и тот же светофор сколько угодно раз, даже если светофор изначально не сломан. Главное условие — каждый сломанный светофор должны починить хотя бы 1 раз. Абаю стало интересно — сколько есть различных наборов бригад, которые могут починить все сломанные светофоры. Два набора бригад считаются различными, если в одном наборе есть такая бригада, которой нет в другом наборе. Так как ответ может быть довольно огромным, выведите его остаток от деления на $$$10^9 + 7$$$.
В первой строке входных данных задано натуральное число $$$N$$$ — количество перекрестков ($$$1 \leq N \leq 5000$$$).
Во второй строке задается бинарная строка длины $$$N$$$, состоящая из символов 0 или 1. $$$i$$$-й символ в строке равен 0, если $$$i$$$-й светофор сломан, иначе 1.
В третьей строке дается целое число $$$M$$$ — количество бригад ($$$1 \leq M \leq 5000$$$).
Далее идут $$$M$$$ строк, каждая из них содержит по 2 числа $$$L_i$$$ и $$$R_i$$$ — описание $$$i$$$-й бригады ($$$1 \leq L_i \leq R_i \leq N$$$).
Гарантируется, что не существует двух разных бригад $$$i$$$ и $$$j$$$, что $$$L_i = L_j$$$ и $$$R_i = R_j$$$.
Выведите единственное число — количество подходящих наборов бригад по модулю $$$10^9 + 7$$$.
4 0000 2 1 4 2 3
2
У вас есть $$$n$$$ точек с координатами $$$(x_i,y_i)$$$. У каждой точки есть вес $$$p_i$$$
Вес ребра между двумя точками $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$ равен величине $$$|x_1-x_2| * |y_1-y_2|$$$.
Назовем путь в возрастающим если веса вершин на этом пути возрастают.
Длина пути - сумма весов ребер.
Вам даны $$$m$$$ отрезков $$$(l_i, r_i)$$$.
Для каждого отрезка выведите длину возрастающего пути состоящего из всех точек $$$(x_l, y_l), (x_{l + 1}, y_{l + 1})...(x_r, y_r)$$$.
В первой строке два целых числа $$$n, q$$$ $$$(1 \le n, q \le 100000 )$$$ - количество точек и количество отрезков.
В следующих $$$n$$$ строках по три целых числа $$$x_i, y_i, p_i$$$ $$$(1 \le x_i, y_i \le 100000)$$$ - описание точек.
Гарантируется, что все $$$p_i$$$ — различные целые числа от $$$1$$$ до $$$n$$$ (то есть они образуют перестановку).
В следующих $$$q$$$ строках по два целых числа $$$l_i, r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$ - описание отрезков.
Для каждого отрезка, выведите ответ.
10 10 61 59 3 97 16 9 2 94 8 57 48 2 91 93 10 30 50 5 75 93 6 67 6 1 61 60 4 56 56 7 9 10 4 6 9 10 3 5 8 10 4 9 2 3 1 7 5 10 2 7
20 2677 20 2619 344 2713 7410 10203 4567 9934
Во время карантина Данияру стало очень скучно, и теперь, чтобы проветриться, он решил походить по своим любимым магазинам.
В городе $$$N$$$ перекрестков. Перекрестки пронумерованы числами от $$$1$$$ до $$$N$$$. Между этими перекрестками расположены $$$M$$$ двусторонних дорог. Во время карантина нельзя свободно перемещаться, для того чтобы проехать по какой-то дороге, нужно иметь специальный пропуск для этой дороги. Данияр живет на перекрестке $$$1$$$. У него $$$K$$$ любимых магазинов, расположенных на перекрестках $$$A_1,A_2,..,A_K$$$. Получения одного пропуска занимает очень много времени, поэтому Данияр хочет узнать какое минимальное количество пропусков ему необходимо, чтобы он мог свободно передвигаться между своим домом и любимыми магазинами. Помогите ему.
В первой строке находятся три целых числа $$$N,M$$$ и $$$K(1 \le N,M \le 10^5, 1 \le K \le 4)$$$.
Во второй строке находятся $$$K$$$ целых числа $$$A_1,A_2,..,A_K(1 \le A_i \le N)$$$.
В следующих $$$M$$$ строках находятся по два целых числа $$$U_i,V_i(1 \le U_i , V_i \le N, U_i \ne V_i)$$$ — означающая, что есть дорого между двумя этими перекрестками.
Гарантируется, что граф связный, то есть от каждого перекрестка можно добраться до каждого другого перекрестка. Между каждой парой перекрестков проходит не более одной дороги.
Выведите минимальное количество пропусков необходимое Данияру.
6 7 2 2 3 1 5 1 6 3 5 3 4 2 4 3 6 2 6
3
4 3 3 1 3 3 1 2 2 3 3 4
2
Есть $$$n$$$ студентов. У каждого студента есть уровень силы в олимпиадах. Причем у всех студентов уровни силы различные. Сила $$$i$$$-го студента равна $$$s_i$$$. Проводится парная олимпиада. Студентов нужно разбить на пары. Если $$$i$$$-й студент и $$$j$$$-й студент будут в одной паре, то сила их пары будет $$$min(s_i, s_j)$$$. Вы хотите разбить студентов так, чтобы сумма сил пар была максимальной. Каждый студент может быть максимум в одной паре. К несчастью, $$$n$$$ - нечетно. В любом случае один из студентов останется без пары. Для каждого студента вы хотите найти максимальную сумму разбиения на пары, в случае если этот студент останется без пары.
В первой строке задано одно целое число $$$n$$$ $$$(3 \le n \le 3 * 10^5$$$, $$$n$$$ - нечетно) – количество студентов. Во второй строке задан массив $$$s$$$ – сила студентов. Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ выполняется $$$(1 \le s_i \le 10^9)$$$. Гарантируется, что все числа в массиве $$$s$$$ различные.
Выведите $$$n$$$ целых чисел. $$$i$$$-ое из них – ответ на задачу, если $$$i$$$-й студент останется без команды.
3 3 1 2
1 2 1
Вы играете в игру Строители! Чтобы победить нужно составить заданную таблицу из $$$N$$$ строк и $$$M$$$ столбцов. Вам изначально дается таблица со сторонами $$$1$$$ на $$$1$$$ в котором написано $$$1$$$. Пусть $$$H$$$ это будет количество cтрок в вашей таблице, а $$$W$$$ будет количество столбцов. Изначально они оба равны $$$1$$$. У вас есть $$$4$$$ действия:
1) действие $$$U$$$ дополняет таблицу сверху строкой состоящей из первых $$$W$$$ чисел слева-направо, которые еще ранее не были использованы. После этого $$$H$$$ увеличивается на $$$1$$$.
2) действие $$$D$$$ дополняет таблицу снизу строкой состоящей из первых $$$W$$$ чисел слева-направо, которые еще ранее не были использованы. После этого $$$H$$$ увеличивается на $$$1$$$.
3) действие $$$L$$$ дополняет таблицу слева столбцом состоящей из первых $$$H$$$ чисел сверху-вниз, которые еще ранее не были использованы. После этого $$$W$$$ увеличивается на $$$1$$$.
4) действие $$$R$$$ дополняет таблицу справа столбцом состоящей из первых $$$H$$$ чисел сверху-вниз, которые еще ранее не были использованы. После этого $$$W$$$ увеличивается на $$$1$$$.
Таблица заполняется только положительными натуральными числами.
Найдите последовательность действий при которых можно восстановить данную таблицу. Гарантируется, что это можно сделать.
Первая строка состоит из $$$N$$$, $$$M$$$ $$$(1 \le N, M \lt = 500)$$$. Следующие $$$N$$$ строк содержат по $$$M$$$ чисел, которые задают таблицу. Все числа от $$$1$$$ до $$$N$$$ * $$$M$$$ и все различные.
В единственной строке выведите строку содержащую буквы $$$L$$$, $$$R$$$, $$$U$$$, $$$D$$$ - действия при которых составляется заданная строка.
3 3 5 2 3 6 1 4 7 8 9
URLD
4 4 13 7 8 9 14 3 1 5 15 4 2 6 16 10 11 12
DLRUDL
Пример заполнения таблицы:
Задан массив $$$A$$$ размером $$$N \times M$$$, заполненный натуральными числами. Строки массива пронумерованы от 1 до $$$N$$$ сверху вниз. Столбцы пронумерованы от 1 до $$$M$$$ слева направо. Клетку в строке номер $$$i$$$ и столбце номер $$$j$$$ назовем $$$A_{ij}$$$. Подпрямоугольником с координатами $$$x_1, y_1, x_2, y_2$$$ ($$$x_1 \leq x_2$$$ и $$$y_1 \leq y_2$$$) назовем множество всех клеток $$$A_{ij}$$$, для которых выполняется условие: $$$x_1 \leq i \leq x_2$$$ и $$$y_1 \leq j \leq y_2$$$. Введем функцию $$$f$$$($$$x_1, y_1, x_2, y_2$$$) (при этом так же $$$x_1 \leq x_2$$$ и $$$y_1 \leq y_2$$$), которая обозначает количество таких простых чисел $$$p$$$, что каждое число $$$A_{ij}$$$ в подпрямоугольнике с координатами $$$x_1, y_1, x_2, y_2$$$ делится нацело на $$$p$$$. Требуется посчитать сумму $$$f$$$($$$x_1, y_1, x_2, y_2$$$) по всем возможным подпрямугольникам.
На первой строке выходных данных заданы два числа — $$$N$$$ и $$$M$$$ ($$$1 \leq N, M \leq 1000$$$) — размеры массива.
Далее следуют $$$N$$$ строк, каждая строка содержит по $$$M$$$ натуральных чисел — элементы массива $$$A$$$ ($$$1 \leq A_{ij} \leq 10^6$$$).
Выведите одно число — ответ на задачу.
2 2 9 6 6 12
14
4 4 7 6 8 9 8 7 7 9 3 6 6 1 5 10 3 7
29
В первом примере существует лишь 9 подпрямоугольников:
1) Для [9] ответ 1
2) Для [6] ответ 2
3) Для [6] ответ 2
4) Для [12] ответ 2
5) Для [9, 6] ответ 1
6) Для [9, 6] ответ 1
7) Для [6, 12] ответ 2
8) Для [6, 12] ответ 2
9) Для [9, 6, 6, 12] ответ 1
Итого 14.
Из-за карантина Абай вынужден общаться с друзьями через компьютер. Когда он с ними общается, то повышает громкость динамика, чтобы лучше слышать их. После того, как он заканчивает с ними общаться, то обратно понижает громкость. Сейчас громкость составляет $$$X$$$, ему необходимо сделать громкость равной $$$Y$$$. За 1 секунду Абай может увеличить или уменьшить громкость на 1 либо на $$$Z$$$. При этом громкость не может быть меньше 0 или больше 100, потому что так устроен компьютер. Найдите минимальное время, за которое Абай сможет достичь своей цели.
В единственной строке вводятся 3 целых числа $$$X, Y, Z$$$ ($$$0 \leq X, Y, Z \leq 100$$$).
Выведите минимальное время в секундах.
0 10 3
4
10 0 3
4
В первом примере Абаю достаточно 3 раза повысить громоксть на 3, а затем 1 раз на 1. Второй пример является обратным первому.