| | | |
|
Сбалансированные подмножества
Динамическое программирование по подстрокам
Суффиксный массив
Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек, помеченная упорядоченными парами (i,j) для всех 1≤i≤N, 1≤j≤N (1≤N≤150). Некоторые из этих ячеек содержат траву.
Непустое подмножество ячеек решётки называется "сбалансированным", если выполняются следующие условия:
Все ячейки подмножества содержат траву.
Подмножество 4-связное. Другими словами, существует путь из любой ячейки подмножества в любую другую ячейку подмножества такой, что две последовательные ячейки пути соседствуют горизонтально или вертикально.
Если ячейки (x1,y) (x2,y) (x1≤x2) есть часть подмножества, то все ячейки (x,y) с x1≤x≤x2 также часть подмножества.
Если ячейки (x,y1) and (x,y2) (y1≤y2) есть часть подмножества, то все ячейки (x,y) with y1≤y≤y2 также часть подмножества.
Посчитайте количество сбалансированных подмножеств по модулю 109+7.
Входные данные:
Первая строка содержит число N.
Каждая их последующих N строк содержит строку из N символов. j-ый символ строки i сверху равен G если ячейка (i,j) содержит траву или символ . в противном случае.
Выходные данные:
Количество сбалансированных подмножеств по модулю 109+7.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
2
GG
GG |
13 |
Для этого теста все 4-связные подмножества сбалансированные.
G. .G .. .. GG .G .. G. GG .G G. GG GG
.., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG |
| 2 |
4
GGGG
GGGG
GG.G
GGGG |
|
642
Ниже пример подмножества, которое удовлетворяет второму условию (4-связности), но не удовлетворяет третьему условию:
GG..
.G..
GG..
.... |
| |
![]()
|
|
Казино
Динамическое программирование по подстрокам
Вновь открытое казино предложило оригинальную игру.
В начале игры крупье выставляет в ряд несколько фишек разных цветов. Кроме того, он объявляет, какие последовательности фишек игрок может забирать себе в процессе игры. Далее игрок забирает себе одну из заранее объявленных последовательностей фишек, расположенных подряд. После этого крупье сдвигает оставшиеся фишки, убирая разрыв. Затем игрок снова забирает себе одну из объявленных последовательностей и так далее. Игра продолжается до тех пор, пока игрок может забирать фишки.
Рассмотрим пример. Пусть на столе выставлен ряд фишек rrrgggbbb, и крупье объявил последовательности rg и gb. Игрок, например, может забрать фишки rg, лежащие на третьем и четвёртом местах слева. После этого крупье сдвинет фишки, и на столе получится ряд rrggbbb. Ещё дважды забрав фишки rg, игрок добьётся того, что на столе останутся фишки bbb и игра закончится, так как игроку больше нечего забрать со стола. Игрок мог бы действовать и по-другому — на втором и третьем ходах забрать не последовательности rg, а последовательности gb. Тогда на столе остались бы фишки rrb. Аналогично, игрок мог бы добиться того, чтобы в конце остались ряды rrr или rbb.
После окончания игры полученные фишки игрок меняет на деньги. Цена фишки зависит от её цвета.
Требуется написать программу, определяющую максимальную сумму, которую сможет получить игрок.
Входные данные
В первой строке входных данных содержится число K (1 ≤ K ≤ 26) — количество цветов фишек. Каждая из следующих K строк начинается со строчной латинской буквы, обозначающей цвет. Далее в той же строке через пробел следует целое число Xi (1 ≤ Xi ≤ 150, i = 1..K) — цена фишки соответствующего цвета.
В (K+2)-ой строке описан ряд фишек, лежащих на столе в начале игры. Ряд задаетсяL строчными латинскими буквами (1 ≤ L ≤ 150), которые обозначают цвета фишек ряда.
В следующей строке содержится число N(1 ≤ N ≤ 150) — количество последовательностей, которые были объявлены крупье. В следующих N строках записаны эти последовательности. Гарантируется, что сумма длин этих N строк не превосходит 150 символов, и все они непустые.
Выходные данные
Выведите единственное целое число — максимальную сумму денег, которую может получить игрок.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
v 3
l 1
u 2
luvu
3
luv
vul
uuu |
6 |
| |
![]()
|
|
Восстановление скобок
Динамическое программирование: два параметра
Динамическое программирование по подстрокам
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.
Входные данные
Вводится строка, которая содержит заданный шаблон длиной не более 80 символов.
Выходные данные
Выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2·109.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
????(? |
2 |
| |
![]()
|
|
Уравнение с пропущенными цифрами
Динамическое программирование
Динамическое программирование по подстрокам
Задано уравнение вида A+B=C, где A, B и C - неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса (?). Примером такого уравнения является ?2+34=4?. Требуется так подставить вместо знаков вопроса цифры, чтобы это равенство стало верным, либо определить, что это невозможно. Найти только одно из возможных решений.
Входные данные
Вводится строка, представляющая собой заданное уравнение без пробелов. Длина уравнения не превышает 80 символов.
Выходные данные
Требуется вывести верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение "No solution".
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
??2?4+9?=355 |
00264+91=355 |
| |
![]()
|
|
Наименьшая сумма ASCII кодов
Динамическое программирование по подстрокам
Вам даны две строки s1 и s2. Вы можете удалить из обоих строк любое количество символов. Ваша цель сделать строки одинаковыми.
Найдите наименьшую сумму ASCII кодов всех удаленных символов.
Входные данные
Программа получает на вход две строки s1 и s2.
Ограничения
1 <= длина s1 и s2 <= 1000;s1 и s2 состоят из маленьких английских букв.
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
sea
eat
|
231
|
Удаление "s" из слова "sea" добавляет к сумме ASCII код буквы "s" (115).
Удаление буквы "t" из слова "eat" добавляет к сумме 116.
В итоге обе строки равны, а 115 + 116 = 231 - минимально возможная сумма для достижения этой цели. |
| |
![]()
|
|
Идентичные строки
Динамическое программирование по подстрокам
Вам даны две строки s1 и s2. За один шаг вы можете удалить из любой строки ровно один символ. Определите минимального количество шагов, необходимое для того, чтобы сделать строки s1 и s2 идентичными.
Входные данные
Программа получает на вход две строки s1 и s2.
Ограничения
1 <= длина s1 и s2 <= 500;s1 и s2 состоят из маленьких английских букв.
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
sea
eat
|
2
|
Вам нужно сделать один шаг, чтобы превратить "sea" в "ea", и еще один шаг, чтобы превратить "eat" в "ea". |
| |
![]()
|
|
Почти палиндром
Динамическое программирование по подстрокам
Слово называется палиндромом, если его первая буква совпадает с последней, вторая – с предпоследней и т.д. Например: "abba", "madam", "x".
Для заданного числа K слово называется почти палиндромом, если в нем можно изменить не более K любых букв так, чтобы получился палиндром. Например, при K = 2 слова "reactor", "kolobok", "madam" являются почти палиндромами (подчеркнуты буквы, заменой которых можно получить палиндром).
Подсловом данного слова являются все слова, получающиеся путем вычеркивания из данного нескольких (возможно, одной или нуля) первых букв и нескольких последних. Например, подсловами слова "cat" являются слова "c", "a", "t", "ca", "at" и само слово "cat" (а "ct" подсловом слова "cat" не является).
Требуется для данного числа K определить, сколько подслов данного слова S являются почти палиндромами.
Входные данные
В первой строке вводятся два натуральных числа:N (1 ≤ N ≤ 5 000) – длина слова и K (0 ≤ K ≤ N).
Во второй строке содержится слово S, состоящее из N строчных латинских букв.
Выходные данные
Требуется вывести одно число – количество подслов слова S, являющихся почти палиндромами (для данного K).
| |
![]()
|
|
Упаковка символов
Динамическое программирование: два параметра
Динамическое программирование по подстрокам
Билл пытается компактно представить последовательности прописных символов от A до Z с помощью упаковки повторяющихся подпоследовательностей внутри них. Например, один из способов представить последовательность AAAAAAAAAABABABCCD - это 10(A)2(BA)B2(C)D. Он формально определяет сжатые последовательности символов и правила перевода их в несжатый вид следующим образом:
- Последовательность, содержащая один символ от A до Z, является упакованной. Распаковка этой последовательности даёт ту же последовательность из одного символа.
- Если S и Q - упакованные последовательности, то SQ - также упакованная последовательность. Если S распаковывается в S', а Q распаковывается в Q', то SQ распаковывается в S'Q'.
- Если S - упакованная последовательность, то X(S) - также упакованная последовательность, где X - десятичное представление целого числа, большего 1. Если S распаковывается в S', то X(S) распаковывается в S', повторённую X раз.
Следуя этим правилам, легко распаковать любую заданную упакованную последовательность. Однако Биллу более интересен обратный переход. Он хочет упаковать заданную последовательность так, чтобы результирующая сжатая последовательность содержала наименьшее возможное число символов.
Ограничения: длина исходной последовательности от 1 до 100.
Входные данные
В первой строке находится последовательность символов от A до Z.
Выходные данные
В единственной строке выводится упакованная последовательность наименьшей длины, которая распаковывается в заданную последовательность. Если таких последовательностей несколько, можно выводить любую.
| |
![]()
|
|
248
Динамическое программирование по подстрокам
Беси любит играть на мобильном.
Игра начинается с последовательности \(N\) положительных целых чисел
(\(2 \leq N \leq 248\)), каждое в диапазоне \(0 \ldots 40\). На каждом ходу
Беси может взять два числа с равными величинами и заменить их число на 1
больше. (Например, она может заменить две соседние 7 на одну 8). Цель игры -
максимизировать наибольшее число, которое она может получить. Помогите
Беси.
ФОРМАТ ВВОДА (файл 248.in):
Первая строка ввода содержит \(N\), и последующие \(N\) строк дают
последовательность чисел, с которых начинается игра.
ФОРМАТ ВЫВОДА (файл 248.out):
Выведите максимальное число, которое может сгенерировать Беси.
| |
![]()
|
|
E. Удаляем подстроки
Динамическое программирование по подстрокам
SmallR нравится игра под названием «Удаляем подстроки». В этой игре вам дана последовательность целых чисел w, можно изменять последовательность и зарабатывать очки. Единственный тип изменения, доступный в игре (неожиданно, правда?) — удаление подстрок. Более формально, можно выбрать несколько последовательных элементов w и удалить их из последовательности. Обозначим последовательность выбранных элементов как wl, wl + 1, ..., wr. Она должна удовлетворять следующим условиям: - равенство |wi - wi + 1| = 1 должно выполняться для всех i (l ≤ i < r);
- неравенство 2·wi - wi + 1 - wi - 1 ≥ 0 должно выполняться для всех i (l < i < r).
После удаления выбранной подстроки w, вы зарабатываете vr - l + 1 очков. Описанную операцию удаления можно выполнять снова и снова, пока существуют надлежащие подстроки. Также, можно в любой момент завершить игру. Ваша задача — по заданной последовательности w вычислить, какое максимальное количество очков можно получить в игре. Выходные данные Выведите единственное целое число — наибольший общий счет, достижимый в игре. | |
![]()
|
|
Скобки(3)
Динамическое программирование по подстрокам
дп
Динамическое программирование: один параметр
Определим правильные скобочные выражения так:
Пустое выражение - правильное.
Если выражение S правильное, то (S) и [S] также правильные.
Если выражения A и B правильные, то и выражение AB - правильное.
Дана последовательность скобок "(", ")", "[" и "]". Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, то есть такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность, не меняя порядок оставшихся.
Ограничения: исходная последовательность содержит не более 100 скобок.
Входные данные
В первой строке находятся символы (, ), [ и ] без пробелов.
Выходные данные
Выводится искомая последовательность скобок без пробелов.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
([(] |
()[()] |
| 2 |
( |
() |
| |
![]()
|
|
Головоломка умножения
Динамическое программирование по подстрокам
В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от неё. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остаётся только две карты.
Цель игры - убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.
Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки
10 * 1 * 50 + 50 * 20 * 5 + 10 * 50 * 5 = 500 + 5000 + 2500 = 8000.
Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким:
1 * 50 * 20 + 1 * 20 * 5 + 10 * 1 * 5 = 1000 + 100 + 50 = 1150.
Входные данные
В первой строке находится число карт N, во второй - разделённые пробелами N чисел на картах.
Ограничения: 3 <= N <= 100, числа на картах целые от 1 до 100.
Выходные данные
Вывести одно целое число - минимально возможное число очков.
| |
![]()
|
|
Палиндромы
Динамическое программирование по подстрокам
дп
Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть дана строка, в которой записано слово S, состоящее из N прописных букв латинского алфавита. Вычёркиванием из этого слова некоторого набора символов можно получить строку, которая будет палиндромом. Требуется найти количество способов вычёркивания из данного слова некоторого (возможно, пустого) набора символов таких, что полученная в результате строка являлась палиндромом. Способы, различающиеся порядком вычёркивания символов, считаются одинаковыми.
Ограничения: 1 <= N <= 60.
Входные данные
В первой строке записано слово S.
Выходные данные
Вывести одно целое число - количество способов вычёркивания.
| |
![]()
|
|
Расстояние Дамерау-Левенштейна
Динамическое программирование по подстрокам
Одной из наиболее распространенных опечаток при наборе текста является перестановка двух соседних символов, например, вместо слова «программа» набрано слово «прогармма». Расстояние Левенштейна не учитывает такие опечатки: при вычислении расстояния Левенштейна одна перестановка будет считаться за два редактирования (например, удаление и вставка символа).
При вычислении расстояния Дамерау-Левенштейна, помимо операций замены, вставки и удаления символа допускается еще операция перестановки двух соседних символов. При этом между переставленными символами нельзя вставлять другие символы.
Определите расстояние Дамерау-Левенштейна для двух данных строк.
Входные данные
Программа получает на вход две строки, длина каждой из которых не превосходит 1000 символов, строки состоят только из заглавных латинских букв.
Выходные данные
Требуется вывести одно число – расстояние Дамерау-Левенштейна для данных строк.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
XABCDE
ACBYDF
|
4 |
| |
![]()
|
|
Расстояние по Левенштейну
Динамическое программирование по подстрокам
Дана текстовая строка. С ней можно выполнять следующие операции:
- Заменить один символ строки на другой символ.
- Удалить один произвольный символ.
- Вставить произвольный символ в произвольное место строки.
Например, при помощи первой операции из строки "СОК" можно получить строку "СУК", при помощи второй операции - строку "ОК", при помощи третьей операции - строку "СТОК.
Минимальное количество таких операций, при помощи которых можно из одной строки получить другую, называется стоимостью редактирования или расстоянием Левенштейна.
Определите расстояние Левенштейна для двух данных строк.
Входные данные
Программа получает на вход две строки, длина каждой из которых не превосходит 1000 символов, строки состоят только из заглавных латинских букв.
Выходные данные
Требуется вывести одно число – расстояние Левенштейна для данных строк.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
ABCDEFGH
ACDEXGIH
|
3 |
| |
![]()
|
|
Вупсень и Пупсень 2
Динамическое программирование по подстрокам
Как вы уже знаете, Вупсень очень любит давать задачи на поиск наибольшей общей подпоследовательности, а Пупсень очень любит давать задачи на поиск наибольшей правильной скобочной подпоследовательности. Лунтик решил обрадовать своих друзей и подарить им на новый год две строки. Конечно же, Вупсень и Пупсень сразу, не посмотрев на строки, захотели дать задачу на поиск наибольшей общей правильной скобочной подпоследовательности, но не тут то было: в этих строках не было скобок. Лунтик понимал, что если Вупсень и Пупсень увидят решения с битсетами, то будут грустить, и весь праздник испортится, поэтому он придумал другую задачу: найдите длину наибольшего общего подпалиндрома.
Подпалиндромом называется такая попоследовательность строки, которая читается справа налево также, как и слева направо.
Формат входный данных
В первой строке дана строка s, во второй строке строка t, состоящие из строчных латинских букв. 1 <= |s|, |t| <= 50.
Формат выходных данных
Выведите одно целое число n - длину наибольшей общей подпоследовательности, являющейся палиндромом.
Примеры
|
Ввод |
Вывод |
|
mem
kek
|
1 |
|
acab
abca
|
3 |
(с) Буков Антон, 11и
| |
![]()
|