Исследуя руины некоторого древнего города, археологи нашли огромную стену с записанным на ней массивом целых неотрицательных чисел $$$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$$$.
43 2 4 5
5
61 2 4 1 1 0
6
Спустя годы поисков, разочарований и приключений кладоискатели нашли легендарную пещеру, где должен был быть зарыт огромный клад. Однако здесь они не нашли сокровище, а лишь $$$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 210 3 2 20 455 5 5 50
15
7 30 0 5 8 13 17 209 5 7 10 1 8
10
В одном небольшом городе, укрытом от посторонних глаз в горах, археологи наткнулись на таинственную пещеру. Внутри неё они обнаружили древние рукописи, написанные на неизвестном языке. После долгих исследований и расшифровки текста учёные пришли к выводу, что записи принадлежат известной цивилизации, существовавшей тысячелетия назад, и содержат сведения о некоторой математической задаче. Они предполагают, что решение этой задачи может оказаться важным для их исследований, и поэтому просят вас написать программу для её решения.
Условие задачи формулируется следующим образом: массив $$$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$$$, чтобы он стал бугристым.
51 3 5 6 5
3
8-8 4 -6 5 9 -7 8 1
25
Группа ученых из МИФИ работает над очередным экспериментом. Они хотят провести эксперимент с различными заряженными частицами.
Во время эксперимента могут происходить события следующих типов:
Эксперимент может иметь большое значение для последующей работы, поэтому учёные просят вас написать программу, которая проверит правильность результатов.
В первой строке содержится единственное число $$$q\, (1 \le q \le 3 \cdot 10^5)$$$ – количество запросов. Далее в каждой из последующих $$$q$$$ строк содержится очередной запрос в формате, описанном выше.
Гарантируется, что в каждом из них $$$1 \le t \le q$$$ и $$$1 \le x \le 10^9$$$ и что все числа в вводе целые.
На каждый запрос типа $$$4$$$ и $$$5$$$ выведите требуемое число в отдельной строке.
62 10 251 15 11 17 23 3 14
-1 35
171 10 11 10 23 10 1541 20 12 20 152 10 142 30 12 20 1452 10 245
10 30 10 30 10 10 0 -1
Некоторая лаборатория состоит из $$$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 21 2 22 3 63 5 32 5 71 4 54 5 15 6 101 3 10
9
5 6 31 2 22 3 63 5 32 5 71 4 54 5 15 6 141 4 1002 3 10
20
Это интерактивная задача
Размышляя над разными несложными генераторами псевдо случайных чисел, 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$$$ запросов во время взаимодействия, ваша программа должна немедленно завершиться, и вы получите вердикт Неправильный ответ. В противном случае вы можете получить произвольный вердикт.
После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение зависло. Для этого используйте:
13 4 12
? 6 ? 12 ? 998244353 ! 7 5 17
Недавно Мориарти напал на след Шерлока и смог получить данные о важном событии, которое произойдёт ровно тогда, когда по некоторому высокочастотному радиосигналу будет передана в точности строка $$$S$$$.
Однако на этот раз Шерлоку удалось запутать своего главного врага, и он специально передал Мориарти эти сведения. Вместо полезной информации он каждую секунду будет равновероятно отправлять один из символов своего алфавита шифровки. В это время Мориарти будет ждать, пока в строке из полученных символов не появится подстрока, равная $$$S$$$; после этого он тут же прекратит наблюдения.
Сейчас Шерлок очень занят, поэтому он попросил вас определить математическое ожидание количества секунд, которое Мориарти будет наблюдать, пока в потоке не появится строка $$$S$$$. Ответ выведите по модулю $$$998244353$$$.
Первая строка содержит строку $$$A$$$ ($$$1 \le |A| \le 36$$$), состоящую из строчных латинских букв или цифр, которая представляет набор символов, которые Шерлок будет равновероятно передавать. Гарантируется, что все символы $$$A$$$ различны.
Вторая строка содержит строку $$$S$$$ ($$$1 \le |S| \le 5 \cdot 10^5$$$), которая является последовательностью символов, появления которой будет ждать Мориарти. Гарантируется, что все символы $$$S$$$ содержатся среди символов строки $$$A$$$.
В единственной строке выведите математическое ожидание числа секунд, которое будет ждать Мориарти, по модулю $$$998244353$$$.
011
2
aboaboba
246
andrew13andrew13
16777216