VitebskOpen Junior
Statement is not available in English language
A. Захар и скины
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Захара есть n скинов в его любимой игре. Он хочет выбрать какие-то k из них. Но вот же проблема! Он не знает сколько способов выбрать скины. Помогите Захару посчитать это количество.

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

Вводятся два целых числа n и k. $$$(1 \leq k \leq n \leq 20)$$$

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

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

Пример
Входные данные
2 1
Выходные данные
2

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

raccoon.pavlov решил попутешествовать по миру. Для начала он решил посетить город М. Заехав в отель, raccoon.pavlov начал осматриваться и заприметил холодильник. В холодильнике было множество вещей: гвоздь, два язя, кока-кола, не дочищенный мандарин и … массив $$$a$$$ целых неотрицательных чисел размера $$$n$$$.

Поскольку raccoon.pavlov пока ничем не занят, он решил придумать задачу с этим массивом и загадать её вам. Задача следующая: raccoon.pavlov загадывает целое неотрицательное число $$$x$$$, а вы должны найти в этом массиве непрерывную последовательность элементов максимальной длины, с суммой чисел равной $$$x$$$. Если таких последовательностей несколько, выведите любую.

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

Первая строка входных данных содержит два целых числа $$$n, x$$$ ($$$1 ≤ n ≤5 \cdot 10^6$$$, $$$0 ≤ x ≤ 10^{16}$$$) — длина массива $$$a$$$ и загаданное число $$$x$$$.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$0 ≤ a_i ≤ 10^9$$$).

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

В единственной строке, если такая последовательность существует, выведите через пробел два целых числа $$$mx$$$ и $$$id$$$ $$$(1≤mx, id≤n)$$$ $$$-$$$ максимальная длина последовательности, с суммой чисел равной $$$x$$$ и индекс её первого элемента. Иначе, если такой последовательности нет, выведите $$$-1$$$.

Система оценки
ГруппаБаллыДоп. ограниченияНеобх. группыКомментарий
$$$0$$$$$$0$$$——Тест из условия
$$$1$$$$$$37$$$$$$n\leq 500$$$——
$$$2$$$$$$23$$$$$$n\leq 3000$$$$$$1$$$—
$$$3$$$$$$18$$$$$$n,x \leq 10^5, a_i = i$$$——
$$$4$$$$$$12$$$$$$n \leq 5 \cdot 10^5$$$$$$2$$$—
$$$6$$$$$$10$$$—$$$2, 3, 4$$$—
Примеры
Входные данные
6 5
1 1 1 1 2 1
Выходные данные
4 3
Входные данные
5 11
4 2 9 0 1
Выходные данные
3 2

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

EgorSav - один из самых ленивых людей. Но к сожалению для него, ему нашлась работа. Ему была выдана строка $$$s$$$ длины $$$n$$$, состоящая из строчных латинских букв. Ему была поручена задача - сделать из этой строки более красивую строку. Красивой строкой называется строка, у которой первая часть состоит из некоторого количества букв a, потом вторая часть - из букв b и так далее до последней части - из букв z. То есть строка будет иметь вид: aaabbccc…..zz.

Чтобы сделать строку красивой, EgorSav может применять такую операцию: выбрать произвольное число $$$j$$$ ($$$1 ≤ j ≤ n$$$) и заменить $$$s_j$$$ на любой другой символ.

Поскольку EgorSav достаточно ленив, он хочет сделать строку $$$s$$$ красивой за минимальное количество операций. Вы должны ему в этом помочь, выведите минимальное количество операций, за которое можно сделать строку $$$s$$$ красивой.

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

Первая строка входных данных содержит одно целое число $$$n$$$ ($$$26≤n≤10^6$$$) — длина строки $$$s$$$. Вторая строка входных данных содержит строку $$$s$$$ длины $$$n$$$.

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

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

Система оценки
ГруппаБаллыДоп. ограниченияНеобх. группыКомментарий
$$$0$$$$$$0$$$——Тесты из условия
$$$1$$$$$$18$$$$$$n \leq 30$$$——
$$$2$$$$$$21$$$$$$n \leq 2000$$$$$$1$$$—
$$$3$$$$$$23$$$$$$s_i = a$$$——
$$$4$$$$$$25$$$$$$s_i = $$${$$$a, b $$$}$$$ $$$$$$3$$$—
$$$5$$$$$$13$$$—$$$1, 2, 3, 4$$$—
Примеры
Входные данные
26
baabbbbbbabbbababbbbabaaab
Выходные данные
26
Входные данные
30
abhdcfjcjfififbfhcgabbdaejfcbj
Выходные данные
24

Statement is not available in English language
D. 12 725 9
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам надо придумать название для этой задачи. Для этого у вас есть массив $$$a$$$ из $$$n$$$ целых чисел. Названием должен быть отрезок из этого массива.

Чтобы вычислить лучшее название, вы решили выполнить $$$q$$$ запросов:

  • «l r»: вычислить красоту отрезка от $$$l$$$ до $$$r$$$, которая вычисляется по формуле: $$$\sum\limits_{l ≤ i≤ j ≤ r} a_i \cdot a_j$$$. То есть вам надо вычислить сумму по всем парам $$$a_i \cdot a_j$$$, по всем $$$l ≤ i≤ j ≤ r$$$. Поскольку значение может получится слишком большим, выведите его по модулю $$$10^9+7$$$.
Входные данные

Первая строка входных данных содержит два целых числа $$$n,q$$$ ($$$1 ≤ n, q ≤5 \cdot 10^5$$$) — длина массива $$$a$$$ и количество запросов.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$0 ≤ a_i ≤ 10^9$$$).

Далее идут $$$q$$$ строк входных данных, которые содержат два числа массив — $$$l$$$ и $$$r$$$ ($$$1 ≤ l ≤ r ≤ n$$$), описание запросов.

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

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

Система оценки
ГруппаБаллыДоп. ограниченияНеобх. группыКомментарий
$$$0$$$$$$0$$$——Тест из условия
$$$1$$$$$$39$$$$$$n, q \leq 500$$$——
$$$2$$$$$$23$$$$$$n, q \leq 3000$$$$$$1$$$—
$$$3$$$$$$15$$$$$$n \leq 3000$$$——
$$$4$$$$$$13$$$$$$l_i = 1$$$——
$$$6$$$$$$10$$$—$$$2, 3, 4$$$—
Пример
Входные данные
5 5
0 3 1 1 0
2 2
2 5
1 3
3 5
1 5
Выходные данные
9
18
13
3
18

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

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

Сейчас правительство объявило о повышении налогов. Повышение налогов сразу приведет к проблемам, поэтому правительство повышает их поэтапно. Если налог увеличится на $$$A$$$, то плата за проезд по всем дорогам увеличится на $$$A$$$.

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

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

В первой строке даны три целых числа $$$N (2 ≤ N ≤ 1 000), M (1 ≤ M ≤ 30 000)$$$ и $$$K (0 ≤ K ≤ 30 000)$$$. Они обозначают количество городов, количество дорог и количество повышений налогов, соответственно.

Во второй строке даны два целых числа $$$S$$$ и $$$D (1 ≤ S, D ≤ N, S \ne D)$$$. Это номера городов отправления и прибытия, соответственно. Города нумеруются в единичной индексации.

В следующих $$$M$$$ строках даны три целых числа $$$a, b (1 ≤ a ≤ N, 1 ≤ b ≤ N, a \ne b), w (1 ≤ w ≤ 1 000)$$$, каждое из которых представляет собой информацию о дороге. Это означает, что город $$$a$$$ и город $$$b$$$ соединены дорогой с платой за проезд $$$w$$$.

В следующих $$$K$$$ строках даны повышения налогов. В каждой строке дано $$$p (1 ≤ p ≤ 10)$$$. Первое, второе и $$$K$$$-ое повышение соответственно.

Гарантируется, что существует путь из $$$S$$$ в $$$D$$$.

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

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

Со второй строки в каждой из следующих $$$K$$$ строк выведите минимальную плату за проезд после первого, второго, ..., $$$K$$$-го увеличения налога.

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

Решение, которое работает при $$$N \times M \times K \le 10^7$$$ получает 50 баллов.

Решение, которое работает при $$$K \le 10$$$ получает 20 баллов.

Пример
Входные данные
3 3 2
1 3
1 3 5
1 2 1
2 3 2
1
2
Выходные данные
3
5
8

Statement is not available in English language
F. ROAD TO BE LEGEND
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Ever tried. Ever failed. No matter. Try again. Fail again. Fail better.
— Samuel, Beckket

Решите следующую задачу для $$$T$$$ тестовых случаев.

Есть магазины пронумерованные от $$$1$$$ до $$$10^9$$$ и девушки пронумерованные от $$$1$$$ до $$$N$$$. Каждая девушка хочет выбрать и посетить один из магазинов.

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

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

$$$\bullet$$$ для каждого числа $$$i$$$ от $$$1$$$ до $$$N$$$, девушка, которая имеет номер $$$i$$$, посетит магазин с номером от $$$l_i$$$ до $$$r_i$$$(включительно).

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

Первая строка содержит $$$T$$$ $$$(1 \leq T \leq 2×10^5)$$$ - количество тестовых случаев.

Каждый тестовый случий начинается со строки содержащей единственное число $$$N$$$ $$$(1 \leq N \leq 2×10^5)$$$ - количество девушек.

Далее, в следующих $$$N$$$ строках представлены $$$l_i$$$ и $$$r_i$$$ $$$(1≤l_i \leq r_i \leq 10^9)$$$, разделённые пробелом.

Пусть $$$M$$$ - Сумма $$$N$$$ по всем тестовых случаев. Гарантируется что $$$M$$$ не больше $$$2×10^5$$$.

ГруппаДополнительные ограничениябаллыРома решил, что:
$$$1$$$$$$1 \leq M \leq 100$$$$$$20$$$баллы начисляются за каждый пройденный тест
$$$2$$$$$$1 \leq M \leq 1000$$$$$$20$$$баллы начисляются за каждый пройденный тест
$$$3$$$$$$1 \leq M \leq 10000$$$$$$10$$$баллы начисляются, если пройдены все тесты в группе
$$$4$$$—$$$50$$$баллы начисляются, если пройдены все тесты в группе
Выходные данные

Выведите $$$T$$$ строк, каждая из строка должна содержать "Yes", если каждой девушке можно назначить магазин, иначе "No".

Примеры
Входные данные
2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000
Выходные данные
Yes
No
Входные данные
1
4
1 2
2 3
3 3
1 4
Выходные данные
Yes