Динамическое программирование

Пусть дана строка \(s\), назовём \(F(s)\) строку \(s\) за которой идёт строка \(s\) "циклически сдвинутая" на один символ вправо (последний символ становится новым первым символом). По заданной строке \(s\), коровы строят свою строку бесконечной длины повторя применение \(F\); каждый шаг удваивает длину текущей строки.

Вам дана начальная строка и индекс \(N\), помогите коровам вычислить символ на позиции \(N\), в этой бесконечной строке.

Напомним, подпоследовательность это подмножество \(a(i_1), a(i_2), \ldots, a(i_k)\) элементов из последовательности, где индексы \(i_1 < i_2 < \ldots < i_k\). Мы говорим, что подпоследовательность возрастающая, если \(a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)\).

ФД может переупорядочивать коров следующим образом выбрать любую подпоследжовательность и реверсировать её элементы

Например, если мы имееем список

1 6 2 3 4 3 5 3 4

мы можем реверсировать следующие элементы

1 6 2 3 4 3 5 3 4
  ^         ^ ^ ^

получим

1 4 2 3 4 3 3 5 6
  ^         ^ ^ ^

Заметим, что элементы располагаются на тех же индексах, где они были изначально, оставляя нетронутыми другие элементы.

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

Фермер Джон хочет сыграть с Бесси \(N\) раз (\(1 \leq N \leq 100,000\)). Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД. Но как корова, она очень ленива. Поэтому она хочет играть одним и тем же жестом много раз подряд. В действительности, она хочет переключаться между жестами не более чем \(K\) (\(0 \leq K \leq 20\)) раз за все игры. Например, если \(K=2\), она может играть "копыто" первые игры, затем переключиться на бумагу и в конце играть снова "копыто".

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

Фермер Джон начинает в позиции (\(f_x, f_y\)) и планирует сделать \(N\) шагов, каждый из которых в одном из 4 направлений: 'N' (север), 'E' (восток), 'S'(юг), 'W' запад. Беси начинает в позиции (\(b_x, b_y\)) и делает аналогичные \(M\) шагов. Эти пути могут иметь общие точки. В каждый момент времени ФД может остаться в своей текущей позиции либо сделать один шаг вперёд по своему маршруту (если ещё не достиг финальной позиции). В каждый момент времени (исключая тот момент, когда они находятся в стартовой позиции), энергия, потреблённая их радиоустройствами равна квадрату расстояния между ними.

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

Каждая из этих \(N + M\) коров получает индивидуальную оценку. Однако в текущем году финальное соревнование будет ограничено командой из \(K\) коров (\(1 \leq K \leq 10\)). Поэтому ФД и ФП отбирают по \(K\) коров. Затем они разбиваются на пары: лучшая корова ФД становится в пару с лучшей коровой ФП, вторая корова ФД, становится в пару со второй коровой ФП и т.д. ФД выиграет, если в каждой из этих пар его корова будет иметь более высокую оценку.

Помогите ФД посчитать количество различных способов которыми ФД и ФП могут отобрать своих коров так, чтобы ФД выиграл в соревновании. Точнее, каждая считается каждая различная пара (\(K\) коров от ФД, и \(K\) коров от ФП). Выведите ответ по модулю 1,000,000,009.

ФД начинает свою прогулку в позиции Holstein 1 а заканчивает в позиции Holstein \(H\). Он хочет посетить каждую корову и для удобства ведёт чек-лист посещения коров. Он хочет посещать Holsteins и Guernseys в порядке их нумерации. В последовательности всех \(H+G\) коров, в порядке их посещения, коровы породы Holsteins \(1 \ldots H\) появятся как подпоследовательности (не обязательно непрерывные), аналогично и с коровами породы Guernseys. Другими словами, последовательность всех \(H+G\) коров будет сформирована перемешиванием списка Holsteins пронумерованных \(1 \ldots H\) и списка Guernseys, пронумерованных \(1 \ldots G\).

Когда ФД двигается от одной коровы к другой, преодолевая расстояние \(D\), он тратит \(D^2\) энергии. Помогите ему определить, минимальное количество энергии, требуемое чтобы посетить всех его коров в соответствии с правилами, описанными выше.

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

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

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

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

Вам дана длинная строка \(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\) до \(N\) (\(2\le N\le 16\)). Отношение дружбы между этими коровами может быть смоделировано ненаправленным графом с \(M\) (\(0\le M\le N(N-1)/2\)) ребрами. Две коровы являются друзьями, если и только если между ними есть ребро в этом графе.

За одну операцию Вы можете добавить или удалить одно ребро в этом графе. Посчитайте минимальное количество операций, которое требуется выполнить, чтобы обеспечить следующее свойство в этом графе: Если коровы \(a\) и \(b\) - друзья, тогда для любой другой коровы \(c\) по крайней мере одна из коров \(a\) и \(b\) является другом коровы \(c\).

У Беси есть два массива длины \(N\) (\(1 \le N \le 500\)). \(i\)-ый элемент первого массива есть \(a_i\) (\(1 \le a_i \le 10^6\)). \(i\)-ый элемент второго массива есть \(b_i\) (\(1 \le b_i \le 10^6\)).

Беси хочет разделить два массива на не-пустые подмассивы так что будут выполняться следующие условия:

1. Каждый элемент принадлежит точно 1 подмассиву.
2. Оба массива разделены на одинаковое количество подмассивов - пусть \(k\). То есть, первый массив разделён ровно на \(k\) подмассивов. И второй массив также разделён ровно на \(k\) подмассивов.
3. Для всех \(1 \le i \le k\),, среднее \(i\)-го подмассива слева первого массива строго меньше либо равно среднему \(i\)-го подмассива слева второго массива.

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

Парейдолия – это явление, при котором ваши глаза склонны видеть в изображениях знакомые узоры, которых на самом деле не существует — например, видение лица в облаке. Поскольку фермер Джон постоянно находится рядом с коровами, он часто видит коровьи узоры в повседневных предметах. Например, если он смотрит на строку "bqessiyexbesszieb", глаза фермера Джона игнорируют некоторые буквы и все, что он видит, это «bessiexbessieb» — строка, содержащая два последовательных подстроки, равные "bessie".

Дана строка длиной не более \(2\cdot 10^5\), состоящая только из символов a-z, где каждый символ имеет связанную стоимость удаления, вычислите максимальную количество непрерывных подстрок, равных "bessie", которые вы можете сформировать, удалив ноль или более символов из него, и минимальную общую стоимость символов, которую вам нужно удалить, чтобы сделать это.

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

Формально, у Вас есть дерево с вершинами помеченными \(1\dots N\) (\(2\le N\le 2\cdot 10^5\)) с корнем в вершине \(1\). Каждая вершина изначально не активна. За одну операцию Вы можете переключить одну вершину из неактивного состояния в активное или обратно. Выведите минимально возможную длину последовательности операций, удовлетворяющей обоим нижеуказанным условиям:

• Определим, что поддерево с корнем в вершине \(r\) состоит из всех вершин \(v\) таких, что \(r\) лежит на пути из \(1\) в \(v\) включительно. Для каждого из \(N\) поддеревьев дерева существует момент времени, когда множество активных вершин сосредоточено именно в этом поддереве.
• Каждая вершина неактивна после выполнения всей последовательности операций.

Каждая вершина \(i\) в этом дереве ассоциируется с породой, имеющей целое число пятен \(s_i\). Дисбалансом такого дерева называется максимум \(|s_i-s_j|\) по всем парам \((i,j)\) таким, что \(j\) есть предок \(i\).

Фермер Джон не знает точное значение \(s_i\) для каждой породы, но он знает нижнюю и верхнюю границу этих величин. Ваша задача - назначить значения \(s_i \in [l_i,r_i]\) (\(0\le l_i\le r_i\le 10^9\)) каждой вершине так, чтобы минимизировать дисбаланс этого дерева.

\(N\) (\(1 \leq N \leq 100\)) коров Фермера Джона выстроены в ряд так, что \(i\)-ая корова имеет уровень голода \(h_i\) (целое неотрицательное число). Коровы хотят есть вместе, и единственный способ уменьшить уровень голода его коров - выбрать соседнюю пару коров \(i\) и \(i+1\) и дать каждой из них мешок кукурузы, тем самым уменьшить на 1 уровень голода каждой из них.

ФД хочет кормить своих коров пока у всех у них не станет один и тот же уровень голода - целый, неотрицательный. Хотя он не знает точно уровень голода каждой из своих коров, он знает верхнюю границу уровня голода каждой коровы, то есть уровень голода \(i\)-ой cow \(h_i\) не более \(H_i\) (\(0\le H_i\le 1000\)).

Ваша задача - посчитать по модулю \(10^9+7\) количество комбинаций из \(N\) уровней голода \([h_1,h_2,\ldots,h_N]\) таких, что ФД сможет достичь своей цели.

Беси начинает в ячейке \((1,1)\). Если она находится в ячейке \((x,y)\), она может выполнить одно из следующих действий:

• Если \(y<M\), Беси может переместиться в следующую колонку (увеличивая \(y\) на 1) за цену \(x^2\).
• Если \(x<N\), Беси может переместиться в следующую строку (увеличивая \(x\) на 1) за цену \(c_y\).

ВАм даются \(Q\) (\(1\le Q\le 2\cdot 10^5\)) независимых запросов, каждый в виде \((x_i,y_i)\) (\(x_i\in [1,N], y_i\in [1,M]\)), вычислите минимально возможную цену для Беси переместиться из \((1,1)\) в \((x_i,y_i)\). compute the minimum possible total

По сигналу Фермера Джона некоторые из коров формируют пары так, что

• Каждая пара состоит из двух различных коров \(a\) и \(b\) чьи расположения не далее \(K\) друг от друга (\(1\le K\le 10^9\)); то есть \(|x_a-x_b|\le K\).
• Каждая корова или является частью некоторой пары или не является частью некоторой пары.
• Группировка в пары называется максимальной, если никакие две из неспаренных коров не могут образовать пары.

  Определите интервал возможных сумм весов неспаренных коров. А именно

  • Если \(T=1\), вычислите минимально возможную сумму весов неспаренных коров.
  • Если \(T=2\), вычислите максимально возможную сумму весов неспаренных коров.

  ФОРМАТ ВВОДА (с клавиатуры / stdin):

  Первая строка ввода содержит \(T\), \(N\), \(K\).

  В каждой из последующих \(N\) строк \(i\)-ая строка содержит \(x_i\) и \(y_i\). Гарантируется, что \(0\le x_1< x_2< \cdots< x_N\le 10^9\)

  ФОРМАТ ВЫВОДА (на экран / stdout):

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

Пастбище и амбар расположены на решётке \(N \times N\) (\(2 \leq N \leq 50\)), причём пастбище находится в левом верхнем углу, а амбар - в правом нижнем. Беси хочет попасть в амбар как можно быстрее, поэтому она ходит только вниз и вправо. В некоторых ячейках находятся стоги сена, которые Беси должна обходить.

Беси чувствует себя уставшей, поэтому она хочет изменить направление движения не более \(K\) раз (\(1 \leq K \leq 3\)).

Сколько различных путей имеется у Беси из пастбища в амбар? Два пути считаются различными, если Беси идёт через некоторую ячейку в одном пути и не идёт через неё в другом.

Разбрызгиватель для пшеницы в квадрате \((I,J)\) разбрызгивает на все квадраты ниже и слева: то есть, квадраты \((i,j)\) с \(I \le i\) и \(j \le J\).

Разбрызгиватель для люцерны в квадрате \((I,J)\) разбрызгивает на все квадраты вверху и справа: то есть, квадраты \((i,j)\) с \(i \le I\) b \(J \le j\).

На квадрате до которого достаёт один или более разбрызгиватель для пшеницы может расти пшеница, на квадрате до которого достаёт один или более разбрызгиватель для люцерны может расти люцерна. На квадрате, до которого достают оба типа разбрызгивателей (или ни одного типа разбрызгивателей) не может расти ничего.

Помогите ФД определить количество способов (по модулю \(10^9 + 7\)) установить разбрызгиватели на своём поле, не более одного на квадрат, так, что каждый квадрат будет доставаться только одним типом разбрызгивателя (каждый квадрат будет фертильным).

Некоторые квадраты уже занят коровами, это не запрещает квадрату быть фертильным, но в них не могут быть установлены разбрызгиватели.