2023-2024 ICPC NERC (NEERC), Kyrgyzstan Qualification Contest
A. Много ракушек
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Все ракушки разного веса, но одинакового размера, поэтому к Адилету в сумку может поместиться не более $$$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$$$.

B. Выигрыш
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Снежка заняла первое место на конкурсе красоты в городе Мышкин, и получила приз от спонсора соревнований, авиакомпании Ковёр-Самолет, — путешествие самолетами компании.

Авиакомпания Ковёр-Самолет соединяет авиарейсами некоторые пары из $$$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

C. Дорога
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вдоль дороги в некоторых местах висят фонари.

Фонари висят на разной высоте, некоторые фонари не работают, так что дорога освещена неравномерно — некоторые части освещаются несколькими фонарями, а некоторые вообще не освещены.

Каждый фонарь освещает некоторый интервал. Требуется определить суммарную длину освещенной части дороги.

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

В первой строке находится одно целое $$$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
Примечание

Тестовый пример:

Список освещенных участков дороги:

  • $$$[0; 22]$$$ (фонари $$$2$$$, $$$3$$$ и $$$5$$$);
  • $$$[30; 42]$$$ (фонари $$$1$$$, $$$4$$$).

Суммарно получается $$$(22 - 0) + (42 - 30) = 34$$$.

D. Веселые фонари
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

Помогите Коту определить, может ли он так поменять лампочки, что будет выполняться вышеприведенное правило.

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

В первой строке содержится единственное целое число $$$T$$$ ($$$1 \le T \le 50$$$) — количество тестовых случаев.

Каждая из следующих $$$T$$$ строк содержит описание одного случая — набор целых чисел через пробел:

  • сначала идет $$$N$$$ $$$(1 \le N \le 400)$$$ — количество фонарей в городе;
  • затем идет $$$M$$$ $$$(0 \le M \le \frac{N \cdot (N - 1)}{2})$$$ — количество улиц, соединяющих фонари;
  • далее идет $$$M$$$ пар $$$A_i$$$ $$$B_i$$$ $$$(1 \le A_i, B_i \le N)$$$ — номера фонарей, соединенных $$$i$$$-й улицей.

Между двумя фонарями может быть более одной улицы. Улица может соединять фонарь с самим собой.

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

Для каждого тестового случая выведите единственную строку:

  • YES, если Кот может поменять лампочки так, чтобы все улицы соединяли фонари разных цветов;
  • NO в обратном случае.
Пример
Входные данные
3
7 3 1 2 1 3 6 1
4 4 2 1 3 2 1 4 3 1
4 4 1 3 4 2 4 1 2 3
Выходные данные
YES
NO
YES

E. Старый шифр
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пикар перехватил шифровку боргов и набор каких-то чисел. Он вспомнил, как шифруются такие сообщения.

Ключами являются натуральные числа, переставленные в определенном порядке:

  1. Числа переставляются по возрастанию перевернутого представления числа: 300 переворачивается в 3, 4030 — в 304, 123 — в 321.
  2. При равенстве перевернутых представлений числа переставляются в порядке убывания индексов в начальном массиве.

Записанные числа являются ключами в шифровке.

Требуется помочь Пикару правильно восстановить порядок чисел для расшифровки.

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

В первой строке записано число $$$N$$$ $$$(1 \le N \le 10^5)$$$ — количество чисел в наборе.

Во второй строке через пробел идут $$$N$$$ целых чисел $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — $$$i$$$-е число из набора.

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

Выведите $$$N$$$ целых чисел через пробел — числа из набора в порядке для расшифровки.

Пример
Входные данные
10
10 31 41 3100 310 31000 43 54 1000 14
Выходные данные
1000 10 31000 310 3100 31 41 43 14 54 

F. Чего-то не хватает...
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кот ученый делает ревизию на складе волшебных вещей Сказочного Патруля. Он знает, что каждого типа предметов у сказочно патруля должно быть по $$$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$$$, но для решения задачи вам достаточно гарантий из условия.

G. Есть ли сдача?
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Эквестрии ходят в обращении монеты двух достоинств: $$$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$$$ монет.

Можно показать, что меньшим количеством монет обойтись нельзя.

H. Вместе навсегда
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Группа межгалактических путешественников прилетела к краю вселенной, чтобы просто посмотреть, как он выглядит. Оказалось, что край вселенной — это бесконечная кирпичная стена, в которой есть $$$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$$$-го портала.

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

Выведите единственную строку:

  • YES, если межгалактические путешественники могут все оказаться ровно в одной вселенной, уничтожив за собой все порталы;
  • NO в противном случае.
Примеры
Входные данные
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.

Один из возможных способов сломать все порталы и оказаться на одной стороне:

  • 1B проходит через портал 1 на А-сторону.
  • 2B проходит через портал 2 на А-сторону.
  • 3B проходит через портал 3 на А-сторону.
  • 4B проходит через портал 4 на А-сторону.
  • 1A проходит через портал 1 на B-сторону.
  • 2A проходит через портал 2 на B-сторону.
  • 1А проходит через портал 3 на A-сторону.
  • 2А проходит через портал 4 на A-сторону.

Видно, что все люди оказались на стороне А, пройдя через каждый портал по $$$2$$$ раза.

I. Налоговый вопрос
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Спайк вышел на пенсию и решил заняться малым бизнесом. Он хочет торговать на различных планетах всякой мелочью и платить как можно меньше налогов.

Спайк знает, что налоги $$$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$$$ три перехода (до $$$2$$$, $$$3$$$, $$$4$$$).
  • У планет $$$2$$$, $$$3$$$, $$$4$$$ один переход (до $$$1$$$).

Соответственно, только планета $$$1$$$ попадает в границы диапазона $$$P = 2$$$, $$$Q = 3$$$.