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

Максимум сытости Беси равен \(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\)) установить разбрызгиватели на своём поле, не более одного на квадрат, так, что каждый квадрат будет доставаться только одним типом разбрызгивателя (каждый квадрат будет фертильным).

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

ФД начинает с одного генома и редактирует его, выполняя следующие шаги:

1. Разделяет геном между каждыми двумя последовательными равными символами.
2. Реверсирует каждую из полученных подстрок.
3. Конкатенирует реверсированные подстроки в том же порядке.

Например, если ФД начинает с генома AGGCTTT, то он выполнит следующие шаги:

1. Разделит между последовательными равными символами G и T получит AG | GCT | T | T.
2. Реверсирует каждую подстроку, получит GA | TCG | T | T.
3. Конкатенирует реверсированные подстроки, получит GATCGTT.

К несчастью, после редактирования генома компьютер ФД сломался, и ФД потерял последовательность генома, с которого он начинал. Более того, некоторые части отредактированного генома повредились, заменившись на знак '?'.

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

Бовинополис состоит из ряда из \(N\) пастбищ (\(1 \leq N \leq 3 \cdot 10^5\)), Каждое из которых содержит одну корову типа Holstein или Guernsey.

Правительство Бовинополиса хочет разделить его на некоторое количество непрерывных районов так, чтобы каждый район содержал не более \(K\) пастбищ (\(1 \leq K \leq N\)), и каждое пастбище содержится ровно в одном районе. Поскольку сейчас правительство контролируется Holstein-ами, они хотят найти такой способ разделения на районы, который минимизирует количество районов, в которых коров Guernsey будет больше, чем коров Holstein или столько же сколько Holstein.

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

ФД рассердился. Он приделал к стене счётчик дней с последнего слома. Если слом случился утром, счётчик покажет 0. Если последний слом случился 3 дня назад, счётчик показывает 3. ФД тщательно записывал значение счётчика каждый день.

В конце года ФД решил действовать. Однако с логом некоторые проблемы.

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

\(N\) коров (\(1 \leq N \leq 10^4\)) ФД стоят в ряд, последовательно пронумерованные \(1 \ldots N\). Корова \(i\) имеет \(s_i\) - уровень мастерства в заворачивании подарков. ФД решил объединить коров в команды. Команда состоит из любого последовательного множества коров числом не более \(K\) коров (\(1 \leq K \leq 10^3\)), и корова не может быть более чем в одной команде. Поскольку коровы могут учиться друг у друга, уровень мастерства каждой коровы в команде может быть заменен на уровень мастерства самой мастеровитой коровы.

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

Сколькими способами ФД может покрасить оставшиеся амбары?

€Ја  ­ зЁ­ Ґвбп б Ї®б«Ґ¤®ў вҐ«м­®бвЁ Ё§ \(N\) Ї®«®¦ЁвҐ«м­ле 楫ле зЁбҐ« (\(2 \leq N \leq 262,144\)), Є ¦¤®Ґ ў ¤Ё Ї §®­Ґ \(0 \ldots 40\). ‡  ®¤Ё­ 室 ЃҐбЁ ¬®¦Ґв ‚§пвм ¤ў  б®бҐ¤­Ёе а ў­ле зЁб«  Ё § ¬Ґ­Ёвм Ёе ­  зЁб«® ­  1 Ў®«миҐ (­ ЇаЁ¬Ґа, ®­  ¬®¦Ґв § ¬Ґ­Ёвм ¤ўҐ б®бҐ¤­ЁҐ 7 ­  ®¤­г 8). –Ґ«м ЁЈал - ¬ ЄбЁ¬Ё§Ёа®ў вм §­ зҐ­ЁҐ б ¬®Ј® Ў®«ми®Ј® зЁб« , Є®в®а®Ґ ®­  ¬®¦Ґв Ї®«гзЁвм. Џ®¬®ЈЁвҐ Ґ©.

Џђ€Њ…ђ ‚‚Ћ„Ђ:

4
1
1
1
2

Џђ€Њ…ђ ‚›‚Ћ„Ђ:

3

‚ ЇаЁ¬ҐаҐ ЃҐбЁ б­ з «  б«Ёў Ґв ўв®аго Ё ваҐвмо 1 Ё Ї®«гз Ґв Ї®б«Ґ¤®ў вҐ«м­®бвм 1 2 2 ,   § вҐ¬ б«Ёў Ґв ¤ўҐ ¤ў®©ЄЁ ў 3. ‡ ¬ҐвЁ¬, зв® ­Ґ ®ЇвЁ¬ «м­® б«Ёў вм ЇҐаўлҐ ¤ўҐ Ґ¤Ё­Ёжл.

Ђўв®а: Mark Chen Bessie likes downloading games to play on her cell phone, even though she does find the small touch screen rather cumbersome to use with her large hooves.

She is particularly intrigued by the current game she is playing. The game starts with a sequence of \(N\) positive integers (\(2 \leq N \leq 262,144\)), each in the range \(0 \ldots 40\). In one move, Bessie can take two adjacent numbers with equal values and replace them a single number of value one greater (e.g., she might replace two adjacent 7s with an 8). The goal is to maximize the value of the largest number she can create. Please help Bessie score as highly as possible!