У Захара есть n скинов в его любимой игре. Он хочет выбрать какие-то k из них. Но вот же проблема! Он не знает сколько способов выбрать скины. Помогите Захару посчитать это количество.
Вводятся два целых числа n и k. $$$(1 \leq k \leq n \leq 20)$$$
Выведите ответ на задачу
2 1
2
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
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
Вам надо придумать название для этой задачи. Для этого у вас есть массив $$$a$$$ из $$$n$$$ целых чисел. Названием должен быть отрезок из этого массива.
Чтобы вычислить лучшее название, вы решили выполнить $$$q$$$ запросов:
Первая строка входных данных содержит два целых числа $$$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
Рома изучал экономику и стал торговцем. Он путешествует между двумя городами, стараясь выбрать маршрут с наименьшей платой за проезд. Города соединены дорогами с двусторонним движением, и за проезд по каждой из них взимается плата.
Сейчас правительство объявило о повышении налогов. Повышение налогов сразу приведет к проблемам, поэтому правительство повышает их поэтапно. Если налог увеличится на $$$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
Решите следующую задачу для $$$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