Алгоритмы

По известному порядку выкладывания карт Эльзой определите максимальное количество очков, которое может заработать Беси.

Максимум сытости Беси равен \(T\) (\(1 \le T \le 5,000,000\)). Поедание апельсина увеличивает её сытость на \(A\), а поедание лимона увеличивает её сытость на \(B\) (\(1 \le A, B \le T\)). Дополнительно, если она хочет, Беси может попить воды не более одного раза, что мгновенно уменьшит её сытость вдвое (с округлением вниз).

Помогите определить Беси максимальную сытость, которую она сможет достичь.

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

Однако подождите! Каждая клетка имеет свой цвет, и каждый цвет имеет различные свойства:

• Если клетка red (красная), то в неё ходить нельзя
• Если клетка pink (розовая), то в неё можно ходить
• Если клетка orange (оранжевая), то в неё можно ходить, но Беси станет пахнуть как апельсин.
• Если клетка blue (синяя) , то она содержит пираний, которые позволят Беси пройти только если она пахнет как апельсин.
• Если клетка purple (пурпурная), то Беси проскальзывает в следующую клетку в этом направлении (если только в следующую клетку можно заходить). Если следующая клетка также пурпурная, Беси продолжает скользить, пока не попадёт в не пурпурную клетку или остановится перед непроходимой клеткой. Скольжение одной клетки засчитывается как один шаг. Пурпурные клетки также удаляют запах.

(Пример ниже подробнее поясняет "пурпурные" клетки)

Помогите Беси добраться из левого верхнего угла в правый нижний за минимально возможное количество ходов.

По известному порядку выкладывания карт Эльзой определите максимальное количество очков, которое может заработать Беси.

Максимум сытости Беси равен \(T\) (\(1 \le T \le 5,000,000\)). Поедание апельсина увеличивает её сытость на \(A\), а поедание лимона увеличивает её сытость на \(B\) (\(1 \le A, B \le T\)). Дополнительно, если она хочет, Беси может попить воды не более одного раза, что мгновенно уменьшит её сытость вдвое (с округлением вниз).

Помогите определить Беси максимальную сытость, которую она сможет достичь.

Однако подождите! Каждая клетка имеет свой цвет, и каждый цвет имеет различные свойства:

• Если клетка red (красная), то в неё ходить нельзя
• Если клетка pink (розовая), то в неё можно ходить
• Если клетка orange (оранжевая), то в неё можно ходить, но Беси станет пахнуть как апельсин.
• Если клетка blue (синяя) , то она содержит пираний, которые позволят Беси пройти только если она пахнет как апельсин.
• Если клетка purple (пурпурная), то Беси проскальзывает в следующую клетку в этом направлении (если только в следующую клетку можно заходить). Если следующая клетка также пурпурная, Беси продолжает скользить, пока не попадёт в не пурпурную клетку или остановится перед непроходимой клеткой. Скольжение одной клетки засчитывается как один шаг. Пурпурные клетки также удаляют запах.

(Пример ниже подробнее поясняет "пурпурные" клетки)

Помогите Беси добраться из левого верхнего угла в правый нижний за минимально возможное количество ходов.

Дорога имеет длину ровно 100 миль и Беси едет по ней, пока её не остановит офицер полиции и не вручит ей квитанцию о превышении скорости.

Дорога поделена на \(N\) участков, каждый описывается положительной длиной в милях, а также целым числом - пределом скорости на этом участке, в диапазоне \(1 \ldots 100\) миль в час. Поскольку длина дороги 100 миль, суммарная длина всех \(N\) участков равна 100. Например, дорога может начаться участком в 45 миль со скоростным пределом 70 миль в час, и затем будет участок в 55 миль, со скоростным пределом 60 миль в час.

Движение Беси тоже может быть описано серией участков - \(M\) штук. На каждом участке она проезжает определённое количество миль с определённой целочисленной скоростью. Например, она может ехать 50 миль со скоростью 65, а затем 50 миль со скоростью 55. Суммарная длина всех этих \(M\) участков также равна 100. Трактор ФД может двигаться со скоростью не более 100 миль в час.

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

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

Фермер Джон заметил, что имеется \(N\) (\(1\le N\le 2\cdot 10^5\)) уникальных ID-номеров и для каждого уникального ID \(d_i\) (\(0\le d_i\le 10^9\)), имеется \(n_i\) (\(1\le n_i\le 10^9\)) коров с таким ID.

Эти коровы могут коммуницировать в парах, их секретный метод шифрования имеет одно строгое правило: две коровы могут обмениваться информацией если это не одна и та же корова и сумма их ID-номеров равна или \(A\) или \(B\) (\(0\le A\le B\le 2\cdot 10^9\)). В один момент времени, корова может быть вовлечена только в одну беседу (то есть никакая корова не может быть частью более чем одной пары)

ФД хочет максимизировать количество коммуницирующих пар. Определите максимальное количество бесед, которые могут состоятся в один момент времени.

У Фермера Джона есть \(N\) коров (\(2 \leq N \leq 5\cdot 10^6\)) и пытается заставить их отсортировать неотрицательный целочисленный массив \(A\) длины \(N\), полагаясь на их лень. У него много тяжелых коробок, поэтому он выстраивает коров одну за другой, где корова \(i+1\) находится за коровой \(i\), и дает \(a_i\) коробок корове \(i\) (\(0\le a_i\)).

Коровы по своей природе ленивы, поэтому они всегда ищут способ передать свою работу кому-то другому. От коровы \(1\) до \(N-1\) по порядку каждая корова смотрит на корову позади себя. Если у коровы \(i\) строго больше коробок, чем у коровы \(i+1\), корова \(i\) считает, что это «несправедливо» и отдает одну из своих коробок корове \(i+1\). Этот процесс повторяется, пока каждая корова не будет удовлетворена.

Фермер Джон пометил количество ящиков \(b_i\), которое каждая корова \(i\) держит и создал массив \(B\) из этих величин. Если \(B = sorted(A)\) тогда ФД счастлив. К несчастью. ФД забыл все кроме \(Q\) величин массива \(A\). (\(2 \leq Q \leq \min(N, 100)\)). К счастью, эти величины включают количество ящиков, которое он собирается дать первой и последней корове. Каждое число, которое помнит ФД задано в виде \(c_i \; v_i\), представляющее, что \(a_{c_i}=v_i\). (\(1 \leq c_i \leq N\), \(1\le v_i\le 10^9\)). Определите количество различных способов, которыми могут быть заполнены пропущенные величины так чтобы ФД был счастливым. ответ выводите по модулю \(10^9+7\).

У Фермера Джона есть \(N\) \((1 \leq N \leq 10^5)\) бутылок, которые он хочет наполнить молоком. Каждая бутылка изначально содержит некоторое количество молока \(m_i\) \((0 \leq m_i \leq 10^9)\). Каждый день он берёт \(A\) \((1 \le A \le N)\) бутылок и наполняет одной единицей молока.

К несчастью, Фермер Нхой, соперник ФД по бизнесу, знает об этом процессе ФД и намерен навредить. Каждый день после того, как ФД заполнит свои \(A\) бутылок, ФН незаметно крадёт одну единицу молока из \(B\) \((0 \le B < A)\) различных непустых бутылок. Чтобы оставаться незамеченным, ФН выбирает \(B\) так, чтобы оно было строго меньше чем \(A\).

После \(D\) (\(1 \leq D \leq 10^9\)) дней ФД продаёт своё молоко. Если в бутылке \(M\) единиц молока, он продаёт эту бутылку за \(M^2\) денежных единиц.

Пусть \(P\) - уникальная прибыль, такая, что FJ может гарантировать, что он получит не менее \(P\) прибыли независимо от того, как ведет себя FN, а FN может гарантировать, что FJ получит не более \(P\) прибыли независимо от того, как ведет себя FJ. Выведите значение \(P\) по модулю \(10^9+7\).

Вам дана длинная строка \(S\) из символов M и O и целое число \(K \geq 1\). Посчитайте количество способов разбить \(S\) на подпоследовательности так, что каждая подпоследовательность MOOOO....O с ровно \(K\) O, по модулю \(10^9+7\).

Поскольку строка очень длинная, Вам она не дана точно. Вместо этого Вам дано целое число \(L\) (\(1 \leq L \leq 10^{18}\)), и строка \(T\) длины \(N\) (\(1 \leq N \leq 10^6\)). Строка \(S\) есть конкатенация \(L\) копий строки \(T\).

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

Каждая из \(N\) коров \((1 \le N \le 10^5)\) имеет целую высоту от \(1\) до \(N\). ФД хочет сфотографировать их в определённом порядке. Если коровы с высотами \(h_1, \dots, h_K\) стоят в ряд слева направо, он хочет, чтобы для их высот выполнялись следующие три свойства:

• Чтобы высоты коров сначала возрастали, а потом убывали. Формально, должно существовать такое целое число \(i\), что \(h_1 \le \dots \le h_i \ge \dots \ge h_K\).
• Чтобы рядом стояли коровы с одинаковой высотой. Формально, \(h_i \neq h_{i+1}\) для \(1 \le i < K\).
• Чтобы фотография была симметричной. Формально, если \(i + j = K+1\), then \(h_i = h_j\).

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

Беси анализирует строку из \(N\) (\(3 \leq N \leq 10^5\)) маленьких латинских букв \(s_1s_2 \ldots s_N\). Эльза рассматривает строку \(t\), содержащую три символа как MOO если \(t_2 = t_3\) и \(t_2 \neq t_1\).

Триплет \((i, j, k)\) валидный, если \(i < j < k\) и строка \(s_i s_j s_k\) формирует MOO. Для этого триплета ФД выполняет следующее, чтобы вычислить его величину

• ФД сгибает строку \(s\) на 90-градусов в индексе \(j\)
• Величина триплета - удвоенная площадь \(\Delta ijk\).

Другими словами, величина триплета есть \((j-i)(k-j)\).

Беси задаёт Вам \(Q\) (\(1 \leq Q \leq 3 \cdot 10^4\)) вопросов. В каждом вопросе она даёт Вам два целых числа \(l\) и \(r\) (\(1 \leq l \leq r \leq N\), \(r-l+1 \ge 3\)) и просит Вас определить максимальную величину среди всех валидных триплетов \((i, j, k)\) таких, что \(l \leq i\) и \(k \leq r\). Если валидных триплетов нет, выведите \(-1\).

Решение задачи может потребовать использовать 64-й целый тип (например, "long long" in C/C++).