Адилет поехал отдыхать в теплые края и, как-то гуляя по пляжу, увидел очень красивые ракушки. Ракушки лежали вдоль берега и, чтобы собрать их, нужно было идти вдоль берега и поднимать по одной ракушке.
Все ракушки разного веса, но одинакового размера, поэтому к Адилету в сумку может поместиться не более $$$K$$$ ракушек, вне зависимости от их веса.
Чтобы упростить себе задачу, Адилет хочет поместить в сумку непрерывный отрезок лежащих ракушек, имеющий наибольший возможный вес. Если общее количество ракушек меньше, чем помещается в сумку, то Адилет заберет все ракушки.
Так как Адилет только начал изучать программирование, он не знает как это сделать быстро, так как ракушек очень много, а ему скоро уезжать.
В первой строке дается целое число $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ — количество ракушек, лежащих на берегу.
Во второй строке через пробел записаны $$$N$$$ целых чисел $$$W_i$$$ $$$(1 \le W_i \le 10^6)$$$ — вес $$$i$$$-й по порядку ракушки.
В третьей строке записано целое число $$$K$$$ $$$(1 \le K \le 10^7)$$$ — максимальное количество ракушек, которое может поместится в сумку к Адилету.
Выведите единственное целое число — максимальный вес ракушек, которые помещаются в сумку к Адилету.
10 1 3 2 4 1 5 1 2 1 2 5
15
Тестовый пример:
В сумку к Адилету помещается не более $$$5$$$ ракушек.
Оптимально взять ракушки со $$$2$$$-й по $$$6$$$-ю включительно — веса ракушек будут $$$(3, 2, 4, 1, 5)$$$, что в сумме даёт $$$15$$$.
Снежка заняла первое место на конкурсе красоты в городе Мышкин, и получила приз от спонсора соревнований, авиакомпании Ковёр-Самолет, — путешествие самолетами компании.
Авиакомпания Ковёр-Самолет соединяет авиарейсами некоторые пары из $$$N$$$ аэропортов (будем называть аэропорты $$$1$$$, $$$2$$$, $$$\dots$$$, $$$N$$$). Город Мышкин (а именно там живет Снежка) находится возле аэропорта номер $$$1$$$. Снежка имеет право совершить ровно $$$K$$$ перелетов — таков приз. При этом она начинает путешествие в аэропорту $$$1$$$, и хочет закончить путешествие там же.
Требуется определить, сколько существует способов организовать путешествие. Заметим, что Снежка может посещать какие-то аэропорты (в том числе и первый) многократно. Важно только, чтобы путешествие заканчивалось в $$$1$$$. Путешествия, отличающиеся порядком посещения аэропортов, считаются различными.
В первой строке находятся через пробел три целых числа $$$N$$$, $$$M$$$ и $$$K$$$ $$$(2 \le N \le 100; 1 \le M \le \frac{N \cdot (N - 1)}{2}; 1 \le K \le 60)$$$ — количество аэропортов, количество различных авиарейсов компании и количество перелетов в маршруте Снежки соответственно.
Каждая из следующих $$$M$$$ строк содержит через пробел два целых числа $$$A$$$ и $$$B$$$ $$$(1 \le A, B \le N; A \ne B)$$$ — конечные пункты одного авиарейса. Все авиарейсы – двусторонние, т.е. пара $$$A$$$ $$$B$$$ означает, что есть авиарейсы и из $$$A$$$ в $$$B$$$, и из $$$B$$$ в $$$A$$$.
Гарантируется, что все рейсы указаны не более одного раза.
Вывести одно целое число — количество способов, которыми Снежка может организовать свое путешествие. Гарантируется, что результат не превосходит $$$2 \cdot 10^9$$$.
4 4 4 1 2 1 3 2 4 3 4
8
4 4 3 1 2 1 3 2 4 3 4
0
Все возможные маршруты в примере $$$1$$$:
1-2-4-2-1, 1-2-4-3-1
1-3-4-2-1, 1-3-4-3-1
1-2-1-2-1, 1-3-1-2-1
1-2-1-3-1, 1-3-1-3-1
Вдоль дороги в некоторых местах висят фонари.
Фонари висят на разной высоте, некоторые фонари не работают, так что дорога освещена неравномерно — некоторые части освещаются несколькими фонарями, а некоторые вообще не освещены.
Каждый фонарь освещает некоторый интервал. Требуется определить суммарную длину освещенной части дороги.
В первой строке находится одно целое $$$N$$$ ($$$1 \le N \le 10^4$$$) — количество фонарей.
Каждая из следующих $$$N$$$ строк содержит через пробел два целых числа $$$A_i$$$ и $$$B_i$$$ $$$(-10^9 \le A \lt B \le 10^9)$$$ — начало и конец отрезка, освещаемого $$$i$$$-м фонарем.
Вывести одно целое число — суммарную длину освещенной части дороги.
5 30 40 5 8 3 22 40 42 0 10
34
Тестовый пример:
Список освещенных участков дороги:
Суммарно получается $$$(22 - 0) + (42 - 30) = 34$$$.
Кот ученый гулял ночью по улицам города Мышкина. Он заметил, что по городу во многих местах стоят фонари. Фонари могут стоять только в начале или конце улицы или просто стоять в парках, не соединяя никакие улицы. Один фонарь может стоять в начале или конце нескольких улиц одновременно.
Кот понял, что город хорошо освещен, но заметил, что все фонари светят одним и тем же цветом — желтым. Так как приближался праздник, то Кот подумал, что надо сделать город более веселым и поменять лампочки в некоторых фонарях на другой цвет.
Кот на складе нашел только лампочки белого цвета и потому решил, что он поменяет лампочки так, чтобы два фонаря, соединенные улицей, имели различные цвета.
Помогите Коту определить, может ли он так поменять лампочки, что будет выполняться вышеприведенное правило.
В первой строке содержится единственное целое число $$$T$$$ ($$$1 \le T \le 50$$$) — количество тестовых случаев.
Каждая из следующих $$$T$$$ строк содержит описание одного случая — набор целых чисел через пробел:
Между двумя фонарями может быть более одной улицы. Улица может соединять фонарь с самим собой.
Для каждого тестового случая выведите единственную строку:
37 3 1 2 1 3 6 14 4 2 1 3 2 1 4 3 14 4 1 3 4 2 4 1 2 3
YES NO YES
Пикар перехватил шифровку боргов и набор каких-то чисел. Он вспомнил, как шифруются такие сообщения.
Ключами являются натуральные числа, переставленные в определенном порядке:
Записанные числа являются ключами в шифровке.
Требуется помочь Пикару правильно восстановить порядок чисел для расшифровки.
В первой строке записано число $$$N$$$ $$$(1 \le N \le 10^5)$$$ — количество чисел в наборе.
Во второй строке через пробел идут $$$N$$$ целых чисел $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — $$$i$$$-е число из набора.
Выведите $$$N$$$ целых чисел через пробел — числа из набора в порядке для расшифровки.
1010 31 41 3100 310 31000 43 54 1000 14
1000 10 31000 310 3100 31 41 43 14 54
Кот ученый делает ревизию на складе волшебных вещей Сказочного Патруля. Он знает, что каждого типа предметов у сказочно патруля должно быть по $$$S$$$ штук.
Кот посчитал все предметы и понял, что какого-то типа предметов всего $$$P$$$ штук, причем $$$P \lt S$$$.
Кот выяснил тип каждого из предметов на складе. Помогите Коту понять, какого типа предметов не хватает.
Первая строка содержит одно целое число $$$N$$$ $$$(3 \le N \le 10^5)$$$ — суммарное количество предметов на складе.
Во второй строке содержится $$$N$$$ целых чисел $$$t_i$$$ $$$(-2 \cdot 10^9 \le t_i \le 2 \cdot 10^9)$$$ — тип $$$i$$$-го предмета на складе.
Гарантируется, что существуют такие целые числа $$$P$$$ и $$$S$$$ $$$(1 \le P \lt S \le N)$$$ такие, что каждое значение $$$t_i$$$ встречается ровно $$$S$$$ раз, кроме одного значения, которое встречается ровно $$$P$$$ раз.
Выведите единственное целое число — тип предмета, которого не хватает на складе.
5 5 -3 5 5 -3
-3
Вам неизвестны числа $$$P$$$ и $$$S$$$, но для решения задачи вам достаточно гарантий из условия.
В Эквестрии ходят в обращении монеты двух достоинств: $$$A$$$ силестий и $$$B$$$ силестий.
Искорке хочет купить у Эпплджек несколько яблок за $$$N$$$ силестий. По итогу Искорке необходимо будет отдать сколько-то монет, и Эпплджек возможно отдаст несколько монет на сдачу.
Считать и носить монеты — не самое интересное занятие, поэтому Искорка и Эпплджек хотят найти минимальное суммарное количество монет, которые можно использовать для оплаты И сдачи.
В единственной строке содержатся через пробел целые числа $$$A$$$, $$$B$$$ и $$$N$$$ $$$(1 \le A, B, N \le 10^9)$$$ — достоинства монет в Эквестрии и стоимость покупки соответственно.
В единственной строке выведите единственное целое число — минимальное суммарное количество монет, участвующих в покупке (оплата И сдача).
Если заплатить $$$N$$$ силестий невозможно, используя монеты достоинствами $$$A$$$ и $$$B$$$, то необходимо вывести число $$$0$$$.
3 5 17
5
4 12 22
0
Первый тестовый пример:
В обращении имеются монеты в $$$A = 3$$$ и $$$B = 5$$$ силестий.
Требуется заплатить $$$N = 17$$$ силестий.
Можно заплатить $$$4$$$ монетами достоинством $$$5$$$ и получить $$$1$$$ монету достоинством $$$3$$$ на сдачу.
Всего использовано $$$5$$$ монет.
Можно показать, что меньшим количеством монет обойтись нельзя.
Группа межгалактических путешественников прилетела к краю вселенной, чтобы просто посмотреть, как он выглядит. Оказалось, что край вселенной — это бесконечная кирпичная стена, в которой есть $$$N$$$ порталов. Каждый из этих порталов ведет в соседнюю вселенную, в которой другая группа межгалактических путешественников прилетела к её краю, чтобы просто посмотреть, как он выглядит.
Путешественники подумали, что было бы здорово всем оказаться вместе в какой-то одной вселенной. А чтобы никто ничего не подозревал — уничтожить все порталы в стене.
К счастью, у портала под номером $$$i$$$ есть запас прочности $$$f_i$$$ — если суммарно пройти через этот портал $$$f_i$$$ раз, то он уничтожится.
Перед вами предстоит задача выяснить, могут ли межгалактические путешественники все оказаться ровно в одной вселенной, уничтожив при этом все порталы.
В первой строке заданы через пробел два целых числа $$$A$$$ и $$$B$$$ $$$(1 \le A, B \le 10^9)$$$ — количество межгалактических путешественников, оказавшихся по разные стороны от стены, разделяющей вселенные.
Во второй строке находится число $$$N$$$ $$$(1 \le N \le 10^5)$$$ — число порталов в стене.
В третьей строке расположены через пробел $$$N$$$ целых чисел $$$f_i$$$ $$$(1 \le f_i \le 10^9)$$$ — прочность $$$i$$$-го портала.
Выведите единственную строку:
5 7 2 1 2
NO
4 4 4 2 2 2 2
YES
Первый тестовый пример:
Суммарная прочность порталов равна $$$3$$$, поэтому $$$5$$$ человек никак не смогут перебраться к остальным $$$7$$$.
Второй тестовый пример:
Обозначим людей с одной стороны как 1A, 2A, 3A, 4A, с другой — 1B, 2B, 3B, 4B.
Один из возможных способов сломать все порталы и оказаться на одной стороне:
Видно, что все люди оказались на стороне А, пройдя через каждый портал по $$$2$$$ раза.
Спайк вышел на пенсию и решил заняться малым бизнесом. Он хочет торговать на различных планетах всякой мелочью и платить как можно меньше налогов.
Спайк знает, что налоги $$$i$$$-й планеты зависят от того, на сколько планет можно улететь с $$$i$$$-й планеты через прямой переход.
Оптимально платить налоги на планетах, у которых количество прямых переходов до других планет находится в диапазоне от $$$P$$$ до $$$Q$$$ включительно.
Так как Спайк служил во флоте, у него уже есть список всех планет и прямых переходов между ними.
Помогите Спайку вычислить, на скольки планетах платить налоги оптимально.
Первая строка содержит через пробел два целых числа $$$N$$$ и $$$M$$$ $$$(1 \le N \le 10^4; 0 \le M \le 10^5)$$$ — количество планет в списке Спайка и общее количество прямых переходов соответственно.
Следующие $$$M$$$ строк содержат через пробел по два целых числа $$$a_i$$$ и $$$b_i$$$ $$$(1 \le a_i, b_i \le N; a_i \ne b_i)$$$ — номера планет, соединенных $$$i$$$-м прямым двусторонним переходом.
Последняя строка содержит через пробел два целых числа $$$P$$$ и $$$Q$$$ $$$(1 \le P \le Q \le 10^4)$$$ — минимальное и максимальное количество прямых переходов с планеты для оптимальных налогов.
Выведите единственное целое число — количество планет, на которых платить налоги оптимально.
2 1 1 2 1 2
2
4 3 1 2 1 3 1 4 2 3
1
Первый тестовый пример:
У каждой из двух планет $$$1$$$ и $$$2$$$ ровно один прямой переход.
Данное количество попадает в границы диапазона $$$P = 1$$$ и $$$Q = 2$$$, поэтому на обеих планетах платить налоги оптимально.
Второй тестовый пример:
Соответственно, только планета $$$1$$$ попадает в границы диапазона $$$P = 2$$$, $$$Q = 3$$$.