Весенний кубок МИФИ 2025
A. Загадочный массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Исследуя руины некоторого древнего города, археологи нашли огромную стену с записанным на ней массивом целых неотрицательных чисел $$$a$$$. Приложив немалые усилия, они смогли прочитать древние надписи и понять, что этот массив может открыть им важнейшую информацию об древней цивилизации. Одним из шагов для этого является решение некоторой задачи, связанной с этим массивом.

Над массивом можно производить следующую операцию: выбрать 2 индекса $$$i$$$ и $$$j\, (1 \le i \lt j \le n)$$$, где $$$n$$$ это длина массива $$$a$$$, и затем вычесть 2 из $$$a_i$$$ и добавить 1 к $$$a_j$$$. После каждой операции все элементы массива должны остаться неотрицательными. Необходимо определить максимальное количество операций, которые можно применить к массиву $$$a$$$.

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

Первая строка содержит единственное целое число $$$n\, (1 \le n \le 10^5)$$$ – длину массива $$$a$$$.

Вторая строка содержит $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n\, (0 \le a_i \le 10^9)$$$.

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

В единственной строке выведите максимальное число операций, которые можно выполнить для данного массива $$$a$$$.

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

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

Спустя годы поисков, разочарований и приключений кладоискатели нашли легендарную пещеру, где должен был быть зарыт огромный клад. Однако здесь они не нашли сокровище, а лишь $$$k$$$ ключей от сундуков и загадочное послание. Оказалось, что клад зарыт в $$$n$$$ различных городах, которые соединяет одна быстрая река. Причём в городе $$$i$$$ спрятано $$$a_i$$$ монет.

В данный момент кладоискатели находятся в городе $$$1$$$. Для того чтобы перемещаться между городами, они будут подниматься вверх по реке на своём корабле. Однако им придётся платить $$$c_i$$$ монет на закупку угля, чтобы из города $$$i$$$ добраться до города $$$i+1$$$ – других путей между городами нет.

Кладоискатели в сумме могут открыть не более $$$k$$$ сундуков, но если они приезжают в город $$$i$$$, они не обязательно будут тратить свой ключ на клад здесь. После того как они прекратят поиски сокровища, они смогут поехать обратно без затрат на уголь(можно считать, что спуск вниз по этой реке не требует топлива).

Необходимо определить, какую максимальную прибыль они смогут получить.

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

В первой строке содержатся два целых числа $$$n, k\, (1 \le k \le n \le 10^5)$$$.

Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n\, (0 \le a_i \le 10^9)$$$ – количество монет в каждом городе.

Во третьей строке содержатся $$$n - 1$$$ целых числа $$$с_1, с_2, \ldots, с_{n-1}, (0 \le c_i \le 10^9)$$$ – стоимости перемещения из города $$$i$$$ в город $$$i+1$$$.

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

Выведите максимально возможную прибыль.

Примеры
Входные данные
5 2
10 3 2 20 45
5 5 5 50
Выходные данные
15
Входные данные
7 3
0 0 5 8 13 17 20
9 5 7 10 1 8
Выходные данные
10

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

В одном небольшом городе, укрытом от посторонних глаз в горах, археологи наткнулись на таинственную пещеру. Внутри неё они обнаружили древние рукописи, написанные на неизвестном языке. После долгих исследований и расшифровки текста учёные пришли к выводу, что записи принадлежат известной цивилизации, существовавшей тысячелетия назад, и содержат сведения о некоторой математической задаче. Они предполагают, что решение этой задачи может оказаться важным для их исследований, и поэтому просят вас написать программу для её решения.

Условие задачи формулируется следующим образом: массив $$$b$$$ называется бугристым, если каждый его внутренний элемент (то есть не первый и не последний) строго больше или строго меньше обоих его соседей.

Изначально дан некоторый массив $$$a$$$, состоящий из целых чисел. За одну операцию можно выбрать некоторый элемент массива и увеличить или уменьшить его на 1.

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

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

Первая строка ввода содержит одно целое число $$$n\, (3 \le n \le 10^5)$$$ — длина массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n\, (-10^9\le a_i \le 10^9)$$$ — значения элементов массива $$$a$$$.

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

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

Примеры
Входные данные
5
1 3 5 6 5
Выходные данные
3
Входные данные
8
-8 4 -6 5 9 -7 8 1
Выходные данные
25

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

Группа ученых из МИФИ работает над очередным экспериментом. Они хотят провести эксперимент с различными заряженными частицами.

Во время эксперимента могут происходить события следующих типов:

  • $$$1$$$ $$$x$$$ $$$t$$$ – появляется новая частица энергии $$$x$$$ и типа $$$t$$$.
  • $$$2$$$ $$$x$$$ $$$t$$$ – любая частица типа $$$t$$$ с энергией $$$x$$$ исчезает. Если ни одной такой частицы нет, ничего не изменяется.
  • $$$3$$$ $$$x$$$ $$$t$$$ – энергия всех частиц типа $$$t$$$ увеличивается на $$$x$$$ единиц.
  • $$$4$$$ – требуется вывести сумму энергий всех частиц.
  • $$$5$$$ – требуется вывести минимальную энергию среди всех частиц, если частиц нет – вывести $$$-1$$$.

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

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

В первой строке содержится единственное число $$$q\, (1 \le q \le 3 \cdot 10^5)$$$ – количество запросов. Далее в каждой из последующих $$$q$$$ строк содержится очередной запрос в формате, описанном выше.

Гарантируется, что в каждом из них $$$1 \le t \le q$$$ и $$$1 \le x \le 10^9$$$ и что все числа в вводе целые.

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

На каждый запрос типа $$$4$$$ и $$$5$$$ выведите требуемое число в отдельной строке.

Примеры
Входные данные
6
2 10 2
5
1 15 1
1 17 2
3 3 1
4
Выходные данные
-1
35
Входные данные
17
1 10 1
1 10 2
3 10 1
5
4
1 20 1
2 20 1
5
2 10 1
4
2 30 1
2 20 1
4
5
2 10 2
4
5
Выходные данные
10
30
10
30
10
10
0
-1

E. Лабиринт времени
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Некоторая лаборатория состоит из $$$n$$$ комнат, соединённых $$$m$$$ двусторонними коридорами, для прохождения которых требуется некоторое количество времени. В лаборатории проводились загадочные эксперименты со временем, в результате чего оказалось, что если пройти по некоторому маршруту и посетить при этом какие-то пары коридоров, потраченное время увеличится на некоторую величину, хотя на первый взгляд этого не должно происходить. Главный учёный узнал об этом, и поэтому собирается отправиться в основную комнату лаборатории $$$n$$$, чтобы исправить аномалии. Изначально он находится в комнате $$$1$$$.

Помогите ему определить, какое наименьшее время ему для этого понадобится. Если добраться до комнаты $$$n$$$ из комнаты $$$1$$$ невозможно, выведите $$$-1$$$.

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

В первой строке содержатся 3 целых числа $$$n, m$$$ и $$$k\, (1 \le n \le 10^5,\, 1 \le m \le 10^5,\, 0 \le k \le 5)$$$ – количество комнат в лаборатории, количество коридоров и количество пар особых коридоров.

В следующих $$$m$$$ строках содержатся по 3 числа $$$u, v$$$ и $$$t$$$, означающие, что между комнатами $$$u$$$ и $$$v$$$ есть двусторонний проход, на прохождение которого требуется $$$t$$$ времени $$$(1 \le u,v \le n,\, 1 \le t \le 10^9)$$$.

Далее в $$$k$$$ строках содержатся по 3 числа $$$i,\, j$$$ и $$$t\, (1 \le i,j \le m,\, i \ne j,\, 1 \le t \le 10^9)$$$, означающие, что если на пути от $$$1$$$ до $$$n$$$ учёный посетит и коридор номер $$$i$$$, и коридор номер $$$j$$$ (в любом порядке), то время его пути увеличится на $$$t$$$.

Гарантируется, что все номера $$$2 \cdot k$$$ коридоров, увеличивающих время, различны.

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

В единственной строке выведите ответ на задачу.

Примеры
Входные данные
5 6 2
1 2 2
2 3 6
3 5 3
2 5 7
1 4 5
4 5 1
5 6 10
1 3 10
Выходные данные
9
Входные данные
5 6 3
1 2 2
2 3 6
3 5 3
2 5 7
1 4 5
4 5 1
5 6 14
1 4 100
2 3 10
Выходные данные
20

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

Это интерактивная задача

Размышляя над разными несложными генераторами псевдо случайных чисел, Andrew-13 решил рассмотреть линейный генератор, который характеризуется параметрами $$$a$$$, $$$b$$$ и $$$p$$$ ($$$1 \le a \lt p$$$, $$$0 \le b \lt p$$$, $$$p$$$ – простое число, $$$2 \le p \lt 10^9$$$). На вход генератору подаётся время $$$t$$$, а генератор выводит $$$(at + b) \mod p$$$.

Для того чтобы показать ненадёжность такого генератора, Andrew-13 решил написать программу, которая, не зная чисел $$$a$$$, $$$b$$$ и $$$p$$$, находит их, делая запросы к генератору. При этом программа делает не более $$$13$$$ запросов.

Сможете ли вы написать свою программу, которая справится с этой задачей?

Протокол взаимодействия

В начале каждого теста выбираются числа $$$a$$$, $$$b$$$ и $$$p$$$, соответствующие ограничениям из условия.

Затем ваша программа начинает взаимодействие с интерактором.

Для того чтобы узнать значение ГПСЧ, описанного в условии, выведите «? $$$t$$$» на отдельной строке ($$$0 \le t \lt 10^{18}$$$, $$$t$$$ - целое). Вы получите значение $$$(at + b) \mod p$$$.

Когда программа готова дать ответ, она должна вывести «! $$$a$$$ $$$b$$$ $$$p$$$» на отдельной строке и затем завершиться.

Если вы сделаете более $$$13$$$ запросов во время взаимодействия, ваша программа должна немедленно завершиться, и вы получите вердикт Неправильный ответ. В противном случае вы можете получить произвольный вердикт.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение зависло. Для этого используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
Пример
Входные данные

13

4

12
Выходные данные
? 6

? 12

? 998244353

! 7 5 17

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

Недавно Мориарти напал на след Шерлока и смог получить данные о важном событии, которое произойдёт ровно тогда, когда по некоторому высокочастотному радиосигналу будет передана в точности строка $$$S$$$.

Однако на этот раз Шерлоку удалось запутать своего главного врага, и он специально передал Мориарти эти сведения. Вместо полезной информации он каждую секунду будет равновероятно отправлять один из символов своего алфавита шифровки. В это время Мориарти будет ждать, пока в строке из полученных символов не появится подстрока, равная $$$S$$$; после этого он тут же прекратит наблюдения.

Сейчас Шерлок очень занят, поэтому он попросил вас определить математическое ожидание количества секунд, которое Мориарти будет наблюдать, пока в потоке не появится строка $$$S$$$. Ответ выведите по модулю $$$998244353$$$.

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

Первая строка содержит строку $$$A$$$ ($$$1 \le |A| \le 36$$$), состоящую из строчных латинских букв или цифр, которая представляет набор символов, которые Шерлок будет равновероятно передавать. Гарантируется, что все символы $$$A$$$ различны.

Вторая строка содержит строку $$$S$$$ ($$$1 \le |S| \le 5 \cdot 10^5$$$), которая является последовательностью символов, появления которой будет ждать Мориарти. Гарантируется, что все символы $$$S$$$ содержатся среди символов строки $$$A$$$.

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

В единственной строке выведите математическое ожидание числа секунд, которое будет ждать Мориарти, по модулю $$$998244353$$$.

Примеры
Входные данные
01
1
Выходные данные
2
Входные данные
abo
aboba
Выходные данные
246
Входные данные
andrew13
andrew13
Выходные данные
16777216