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

43 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Строковые артефакты#47938

Команда исследователей-археологов, отправилась в затерянный храм на поиски древних артефактов. На каждом артефакте записана строка, состоящая из символов "0" и "1". Археологи узнали, что выйти из храма с артефактами можно только в том случае, если суммарное количество нулей в строках, записанных на всех, взятых с собой артефактах, будет не больше m, а суммарное количество единиц не больше n. Исследователи хотят унести как можно больше артефактов. Ваша задача определить, какое максимальное количество артефактов исследователи-археологи смогут унести. 

Входные данные
Первая строка содержит целое число k - количество артефактов в храме. Далее идут k строк si; в i-й строке записана строка с i-го артефакта, состоящая из "0" и "1".
На k+2 строке записаны 2 числа: m и n. 
 

Ограничения

  • 1 <= k <= 600
  • 1 <= длина si <= 100
  • si состоит только из цифр '0' and '1'.
  • 1 <= m, n <= 100



Выходные данные
Выведите ответ на задачу.

Пояснения к тестовым примерам
В первом тестовом примере наибольшим подмножеством, содержащим не более пяти 0 и не более трех 1, является {"10", "0001", "1", "0"}, поэтому ответ - 4.
Другие допустимые, но меньшие подмножества  {"0001", "1"} и {"10", "1", "0"}.
Подмножества {"111001"} является недопустимым, так как содержит четыре 1, что больше n.

 

Задача о рюкзаке
✓ 5✗ 331 200средняяВойти и решать
Гирьки: три кучки одного размера#47749
Дан набор гирек массой m1, …, mN. Разделите его на три кучки равной масссы, содержащие равное число гирек.

Входные данные
Первая строка входных данных содержит натуральное число N, не превышающее 18. Далее идет N натуральных чисел mi, не превышающих 100.

Выходные данные
Программа должна вывести номера гирек для каждого из наборов в три строки или строчку No solution, если решения не существует.
Задача о рюкзаке
✓ 2✗ 281 200средняяВойти и решать
Путешествия Аркадия#47162

Магистр Аркадий любит путешествовать на поезде. Он собирается отправиться в множество поездок в течение года и заранее знает, в какие дни он поедет.

Аркадий может купить билеты по разным тарифам:

  • 1-дневный тариф стоит C1 рублей;
  • 7-дневный тариф стоит C2 рублей;
  • 30-дневный тариф стоит C3 рублей.

Каждый билет начинает действовать с того дня, когда был куплен. 
Например, если Аркадий купит 7-дневный билет на 2-й день путешествия, то он  сможет путешествовать 7 дней: 2, 3, 4, 5, 6, 7 и 8 дни.

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


Входные данные
Первая строка содержит натуральное число n - количество дней, в которые Аркадий планирует путешествовать. Вторая строка содержит порядковые номера дней, в которые Аркадий планирует путешествовать (daysi). Третья строка содержит три числа: C1, C2, C3.
 

Ограничения:

  • 1 <= n <= 365
  • 1 <= daysi <= 365
  • Порядковы номера дней daysi даются в строго возрастающем порядке.
  • 1 <= С1, С2, С3 <= 1000


Выходные данные
Выведите минимальное количество рублей, которое Аркадию придется заплатить за билеты.
 
 
Примеры
№ Входные данные Выходные данные
1 
6
1 4 6 7 8 20
2 7 15
 
11
2 
12
1 2 3 4 5 6 7 8 9 10 30 31 
2 7 15
 
17
Динамическое программирование
✓ 12✗ 221 200средняяВойти и решать
Го#47001
Петя играет с Васей в игру Го на доске размером NxM. По окончании игры вся доска была заполнена черными и белыми камешками. Петя играл черными камешками, а Вася - белыми. Теперь Петя хочет узнать квадрат с наибольшей площадью, который состоит только из его камешков. 
Обозначим условно на доске черные камешки единицей, белые камешки - нулем. По заданному расположению камешков на доске, помогите Пете определить площадь такого квадрата.



Входные данные
В первой строке записаны 2 натуральных числа N и M - размер доски для игры в Го. Следующие N строк содержат по M чисел ai,j. Каждое число ai,j= 1 если на этой клетке расположен черный камушек и 0, если на ней расположен белый камушек.
 

Ограничения

  • n == количество строк в матрице
  • m == количество столбцов в матрице
  • 1 <= n, m <= 300
  • a[i][j] это 0 или 1.


Выходные данные
Выведите максимальную площадь квадрата, состоящего из камушков Пети.
 



Рисунок выше относится к примеру № 1
Примеры
№ Входные данные Выходные данные
1 
4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
 
4
2 
2 2
0 1 
1 0
 
1
Динамическое программирование на таблицах
✓ 2✗ 501 200средняяВойти и решать
Ускорители для Деда Мороза#44037

Дед Мороз за ночь должен посетить N городов. У него есть двумерный план расположения всех городов. План нарисован в декартовой системе координат, в которой точкой (0, 0) обозначено место старта Деда Мороза. Каждый город на плане отмечен точкой с координатой (Xi, Yi). Также на карте обозначены M точек с координатами (Pi, Qi), в которых расположены ускорители. Чтобы успеть разнести все подарки, Дед Мороз может воспользоваться ускорителем, который увеличивает его скорость в два раза (а может им и не пользоваться).

Дед Мороз в Новогоднюю ночь начинает с места старта, посещает все N городов и возвращается обратно.

Начальная скорость Деда Мороза равна 1. Найдите наименьшее время, необходимое Деду Морозу, чтобы посетить все города и вернуться обратно. Временем, при котором он раскладывает все подарки будем пренебрегать!



Входные данные
Первая строка входных данных содержит два целых числа N и M (1 <= N <= 12, 0 <= M <=5). Следующие N строк содержат координаты городов (Xi, Yi). Далее идут M строк с координатами ускорителей (Pi, Qi). Все координаты различны и среди них нет координаты (0, 0).

Выходные данные
Выведите ответ на задачу, с точностью не менее 6 знаков после запятой.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 2 1
1 1
0 1
1 0		 2 1
1 1
0 1
1 0		 Вот один из оптимальных способов разнести все подарки
  • Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1.
  • Пройти расстояние 1 от ускорителя 1 до города 1 со скоростью 2, затратив время 0,5.
  • Пройти расстояние 1 от города 1 до города 2 со скоростью 2, затратив время 0,5.
  • Пройти расстояние 1 от города 2 до начала координат со скоростью 2, затратив время 0,5.
2 2 1
1 1
0 1
100 0		 3.4142135624 Вот один из оптимальных способов разнести все подарки
  • Пройти расстояние 1.41... от начала координат до города 1 со скоростью 1, затратив время 1.41....
  • Пройти расстояние 1 от города 1 до города 2 со скоростью 1, затратив время 1.
  • Пройти расстояние 1 от города 2 до начала координат со скоростью 1, затратив время 1.
3 1 2
4 4
1 0
0 1		 4.3713203436 Вот один из оптимальных способов разнести все подарки
  • Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1.
  • Пройти расстояние 1,41... от ускорителя 1 до ускорителя 2 со скоростью 2, затратив время 0,707....
  • Пройти расстояние 5 от ускорителя 2 до города 1 со скоростью 4, затратив время 1,25.
  • Пройти расстояние 5,65... от города 1 до начала координат со скоростью 4, затратив время 1,41....
Алгоритмы на графахДинамическое программирование на таблицахЭлементарная геометрия
✓ 2✗ 181 300средняяВойти и решать
Кайман и пельмешки#40124
Кайману снится необычный сон, будто он попал в странный район города. Этот район можно представить как граф-дерево, где вершины - это перекрестки и ребра - двусторонние дороги, которые соединяют эти перекрестки. Всего перекрестков n и у каждого свой номер от 0 до n-1.

Но не все так плохо в этом сне, ведь на каждой дороге между перекрестками с номерами u и v есть Сu,v пельменей! Кайман очень любит пельмешки, поэтому хочет съесть как можно больше, но есть проблема - если он побывает в каком-либо перекрестке более чем k раз, то на него нападет злой пельменный монстр.

Хоть это и сон, но пельмешки на каждой дороге можно съесть только один раз, хотя ничего не мешает ходить по дорогам по несколько раз. Также Кайман не останавливается на дорогах. То есть, если он начнет переходить от одного перекрестка к другому, то он обязательно пройдет дорогу полностью до следующего перекрестка.

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

Входные данные:
В первой строке следует два целых числа n и k (3 ≤ n ≤ 105; 1 ≤ k ≤ 105) — количество перекрестков и максимальное количество посещений каждого из перекрестков.
В следующих n - 1 строках следует по три целых числа u, v и Cu,v (0 ≤ u, v ≤ n - 1; 0 ≤ Cu,v ≤ 10000), означающих, что перекрестки с номерами u и v связаны дорогой, на которой Cu,v пельменей.
Гарантируется, что перекрестки и дороги формируют дерево.

Выходные данные:
Выведите одно целое число - максимальное количество пельменей, которое сможет съесть Кайман.

Примеры:
 
Входные данные Выходные данные
9 3
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3		 15
9 5
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3		 17
11 6
1 0 7932
2 1 1952
3 2 2227
4 0 9112
5 4 6067
6 0 6786
7 6 3883
8 4 7137
9 1 2796
10 5 6200		 54092

Пояснение:
В первом примере нужно посетить перекрестки в следующем порядке: 0, 1, 5, 1, 3, 1, 0, 2, 6, 2, 7, 2, 8. Тогда он съест суммарно 1+2+2+1+3+3+3 = 15 пельменей.
Обратите внимание, что ни один перекресток не посещается более чем 3 раза.
 
Динамическое программирование на поддеревьях
✓ 6✗ 2871 400средняяВойти и решать
Zuma#40059
Хлоя недавно установила на свой телефон игру «Zuma». Игроку даётся ряд из n драгоценных камней, i-й из которых имеет цвет ci. Цель игры — уничтожить все камни за как можно меньшее количество секунд.

За одну секунду Хлоя может выбрать любую подстроку (последовательность стоящих рядом камней), являющуюся палиндромом, и удалить её. После удаления данной подстроки оставшиеся камни сдвигаются, чтобы снова образовать непрерывный ряд. Какое минимальное количество секунд необходимо, чтобы уничтожить всю строку?

Напомним, что строка (или подстрока) является палиндромом, если она одинаково читается как слева направо, так и справа налево. В данном случае это означает, что цвет первого камня равен цвету последнего камня, цвет второго равен цвету предпоследнего и так далее.

Входные данные:
В первой строке входных данных записано единственное число n (1 ≤ n ≤ 500) — количество камней в изначальном ряду.
Во второй строке записано n целых чисел, i-е из которых равно ci (1 ≤ ci ≤ n) — цвет i-го камня в изначальном ряду.

Выходные данные:
Выведите единственное целое число — минимальное количество секунд, необходимое чтобы удалить все камни.

Примеры:
 
Входные данные Выходные данные
3
1 2 1		 1
3
1 2 3		 3
7
1 4 4 2 3 2 1		 2

Пояснения:
Последовательность в третьем примере: [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> []
Динамическое программирование
✓ 2✗ 411 300средняяВойти и решать
Игра-заливка#40058
Вам дана полоска из клетчатой бумаги из n раскрашенных квадратов, пронумерованных от 1 до n слева направо. Квадрат под номером i изначально покрашен в цвет ci.

Скажем, что квадраты i и j лежат в одной компоненте, если ci = cj и ci = ck для всех k, удовлетворяющих i < k < j. Иначе говоря, все квадраты на отрезке от i до j должны иметь одинаковый цвет.
Например, у полоски [3,3,3] есть 1 компонента связности, а у [5,2,4,4] их 3.

Игра «заливка» играется на этой полоске следующим образом:
В начале игры вы выбираете один произвольный стартовый квадрат (это не считается за ход).
Затем, в каждый ход, вы меняете цвет компоненты связности, содержащей стартовый квадрат на любой другой цвет.

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

Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 5000) — количество квадратов.

Вторая строка содержит целые числа c1,c2,…,cn (1 ≤ ci ≤ 5000) — изначальные цвета квадратов.

Выходные данные:
Выведите одно целое число — минимальное количество ходов, которое нужно сделать.

Примеры:
 
Входные данные Выходные данные
4
5 2 2 1		 2
8
4 5 2 2 1 3 5 5		 4
1
4		 0

Пояснение:
Один из оптимальных способов в первом примере: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]
Динамическое программирование
✓ 2✗ 611 300средняяВойти и решать
K-й путь#38477
У вас есть таблица c N строками и M столбцами. В каждой ячейке таблицы записана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла до правого нижнего угла, если вам разрешено идти только вправо и вниз. Конкатенация букв в порядке обхода составляют строку. Скажем, что эта строка - значение пути. Теперь рассмотрим все такие пути и отсортируем их значения в алфавитном порядке. Ваша задача найти значение K-го пути в этом отсортированном листе.

Входные данные
В первой строке задается два целых числа N - количество рядов и M - количество столбцов заданной таблицы (1 <= N, M <= 30). Каждая из следующих N строк содержит ровно M строчных букв английского алфавита. Последняя строка входного файла содержит целое число K (1 <= K <= 1018). Гарантируется, что для K ответ всегда существует.

Выходные данные
Выведите ответ на задачу

Пояснения к примеру
abcdgk, abcdgk, abcdjk, abfdgk, abfdjk, abfijk, aefdgk, aefdjk, aefijk, aehijk
 
Примеры
№ Входные данные Выходные данные
1 3 4
abcd
efdg
hijk
4		 abfdgk
Динамическое программирование на таблицах
✓ 2✗ 121 200средняяВойти и решать
Энергичная черепаха#38472
Дана сетка с N + 1 рядами и M + 1 столбцами. Черепаха находится на клетке (0, 0) и хочет попасть в клетку (N, M). Черепаха может идти только вверх или вправо. На сетке в K клетках находятся ловушки. Если черепаха пойдет в одну из этих клеток, то она перевернется. У черепашки есть силы для того, чтобы встать не более чем T раз. Посчитайте, сколькими различными путями черепаха может попасть в клетку (N, M). Так как это число может быть очень большим, выведите остаток от его деления на Z.

Входные данные
В первой строке входного файла задается 5 целых чисел: N, M, K, T и Z (1 ≤ N,M ≤ 300000, 0 ≤ K, T  20, 1 ≤ Z ≤ 109). В каждой из следующих K строк расположены координаты соответствующей клетки с ловушкой X, Y (0 ≤ X ≤ N, 0 ≤ Y ≤ M). Гарантируется, что все клетки с ловушками различные и в клетках (0, 0) и (N, M) ловушек нет.

Выходные данные
Выведите требуемое число.
Примеры
№ Входные данные Выходные данные
1 1 1 1 0 100
0 1		 1
2 2 2 0 0 10 6
Динамическое программирование на таблицах
✓ 1✗ 11 300средняяВойти и решать
Splash Bomb#33297
Имеется клетчатое поле размером NxM. В каждой клетке может лежать либо реактив A, либо B, либо ничего не лежать - 0. За ход можно положить в некоторую клетку реактив A, причем преобразование вещества идет по следующему правилу: 0+A->A, A+A->B, B+A->0. При этом в результате последней реакции происходит взрыв, а в соседние непустые клетки по сторонам света (если они есть), попадает по порции реактива A. Очки за ход = количество взрывов минус 1. Очки за отдельные ходы суммируются. Требуется очистить поле и при этом набрать максимальное количество очков.
 
Входные данные
В первой строке вводятся N и M (1 <= N, M <= 3). Далее идут N строк по M символов из алфавита (0, A, B) - описание поля.
 
Выходные данные
Выведите единственное число - максимальное количество очков, которое можно набрать.
 
Комментарий ко второму примеру: за первый ход не произошло ни одного взрыва, очки=0-1=-1; за второй ход произошел один взрыв и поле очистилось, очки=1-1=0; итого очков: 0+(-1)=-1

Ввод Вывод
1 1
0		 0
1 1
A		 -1

Динамическое программированиеЗадачи на моделированиеПеребор
✓ 5✗ 781 200средняяВойти и решать
Обработка больших данных#33128
В научной лаборатории разрабатывается новая архитектура суперкомпьютера,
позволяющая эффективно обрабатывать большие объемы данных.
Суперкомпьютер имеет 2k ячеек памяти, пронумерованных от 0 до 2k– 1. Отрезком
[L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R,
включительно.
Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является
корректным, если его длина (R – L + 1) равна 2i для некоторого i, а число L делится на 2i.
Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются
отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,
6] и [7, 7].
Ключевой операцией в новой архитектуре является операция STORE, которая за одно
действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного
отрезка.
Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить
на суперкомпьютере программу обработки данных, но перед её запуском необходимо
инициализировать память определенным образом. А именно: первые с1 ячеек памяти
необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее,
последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.
Ученым надо выяснить, какое минимальное количество операций STORE необходимо
выполнить, чтобы проинициализировать память требуемым образом.
Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое
содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для
инициализации памяти достаточно трех операций STORE:
- STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;
- STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];
- STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],
как и требуется.
Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не
является корректным отрезком памяти.
Требуется написать программу, которая по заданному содержимому памяти
определяет минимальное количество операций STORE, которое необходимо выполнить для
инициализации памяти заданным образом.

Формат входных данных
Первая строка входных данных содержит три целых числа: k, n и m (0 ≤ k ≤ 30,1 ≤ n ≤ 10
5, 1 ≤ m ≤ 109).
Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа ci
и vi (1 ≤ ci ≤ 2k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2k).
Формат выходных данных
Требуется вывести одно целое число – минимальное количество операций STORE,
которое необходимо выполнить для инициализации памяти заданным образом.
 
Ввод Вывод
3 3 2
1 1
2 2
5 1
 3
Динамическое программированиеМножестваСтруктуры данных
✓ 0✗ 101 300средняяВойти и решать
Мониторинг труб#33124
Газораспределительная система одного региона устроена следующим образом. Она
содержит n узлов, пронумерованных от 1 до n, некоторые узлы соединены односторонними
трубами. Узел с номером 1 соответствует центральному газохранилищу.
Система узлов описывается числами от p2, p3, …, pn. Для всех i от 2 до n узел с
номером pi соединен односторонней трубой с узлом i, газ по этой трубе передается от узла pi
к узлу i. Известно, что возможно доставить газ по трубам от центрального газохранилища до
любого узла системы (возможно, с использованием промежуточных узлов). В системе
используются трубы различных типов, тип трубы обозначается буквой английского алфавита
от «a» до «z». Труба, соединяющая узел pi с узлом i, имеет тип ci.
Для проверки качества труб используется специальный робот. Он помещается в
систему труб в одном из узлов и перемещается по трубам, каждый раз проверяя трубу, по
которой он перемещается. Робот может перемещаться по трубам только в том же
направлении, в котором по трубе передается газ. Совершив одно или несколько
перемещений по трубам между узлами, робот извлекается из системы труб.
Каждый запуск робота должен соответствовать одной из m заданных спецификаций,
пронумерованных от 1 до m. Спецификация с номером t представляет собой строку st,
состоящую из строчных букв английского алфавита. Запуск соответствует спецификации st,
если количество перемещений робота по трубам во время запуска совпадает с длиной st, и
для всех j от 1 до длины st на j-м шаге робот перемещается по трубе, тип которой совпадает с
st[j] —символом на позиции j в спецификации.
Если запуск робота соответствует спецификации с номером t, то стоимость этого
запуска составляет wt. Оператору системы необходимо проверить все трубы, для этого
можно запускать робот несколько раз. Каждый раз выбирается спецификация и маршрут
робота по трубам, соответствующие выбранной спецификации. Необходимо проверить все
трубы так, чтобы суммарная стоимость запусков робота для проверки качества труб была
минимальна. Одну и ту же трубу можно проверять несколько раз.
Требуется написать программу, которая по описанию системы труб и списку
спецификаций определяет минимальную суммарную стоимость запусков робота, в
результате которых все трубы будут проверены, а также список необходимых для этого
запусков (по требованию).
 
Формат входных данных
В первой строке входных данных находятся три целых числа n, m и t — количество
узлов системы труб, количество спецификаций запусков робота и параметр, указывающий,
требуется ли вывести список запусков робота или только их минимальную суммарную
стоимость (1 ≤ n ≤ 500, 1 ≤ m ≤ 105, t равно 0 или 1).
В последующих (n – 1) строках содержится информация о трубах, (i – 1)-я из этих
строк содержит разделенные пробелом значения pi и ci, где pi — целое число, задающее
номер узла, из которого ведет труба в i-й узел, а ci — строчная буква английского алфавита,
задающая тип этой трубы (1 ≤ pi ≤ i – 1).
В последующих m строках содержится информация о спецификациях, i-я из этих
строк содержит разделенные пробелом целое число wi — стоимость запуска робота в
соответствии с этой спецификацией, и состоящую из строчных букв английского алфавита
строку si — саму спецификацию (1 ≤ wi ≤ 109). Суммарная длина строк si не превышает 106.
 
Формат выходных данных
Первая строка выходных данных должна содержать одно число — минимальную
суммарную стоимость запусков робота, в результате которых все трубы будут проверены.
Если проверить все трубы невозможно, требуется вывести «–1».
Если t = 0, то больше ничего выводить не требуется.
Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний
запусков робота. В этом случае вторая строка выходных данных должна содержать
число k — количество запусков робота, которое необходимо выполнить для проверки труб. В
следующих k строках необходимо вывести по три целых числа ai, bi и ci — номер узла, в
котором начинается запуск, номер узла, в котором заканчивается запуск, и номер
спецификации, которой соответствует запуск.
Если оптимальных способов проверки несколько, требуется вывести любой из них.
 
Ввод Вывод
3 3 0
1 a
2 b
3 a
4 b
2 a
 6
7 3 1
1 a
2 a
3 b
3 b
1 b
6 b
3 aab
5 b
2 ab
15
4
1 4 1
2 5 3
1 6 2
6 7 2
 
 
Пояснение к примеру
Система труб, заданная во втором примере входных данных, и оптимальный способ
проверки всех труб для этого случая приведены на рисунке ниже.
 


 
Необходимо обратить внимание на следующие моменты:
- трубу можно проверять несколько раз, так в приведенном примере дважды
проверена труба из узла 2 в узел 3;
- одну и ту же спецификацию разрешается использовать несколько раз, в
приведенном примере вторая спецификация используется дважды, для
проверки труб из узла 1 в узел 6 и из узла 6 в узел 7;
- робот может перемещаться по трубам только в том же направлении, по
которому по трубе передается газ, спецификацию «ab» нельзя использовать
для проверки труб по маршруту 2→1→6, так как робот не может
переместиться из узла 2 в узел 1.
Алгоритмы на графахДеревьяДинамическое программирование
1 300средняяВойти и решать
Шаблон с ? и *#28419
Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.
 
Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблонам, либо выдать сообщение, что такой строки не существует.
 
Входные данные
Заданные шаблоны записаны в первых двух строках входных данных. Длина каждого шаблона не превосходит 80 символов.

Выходные данные
Выведите строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение "No solution!"
 
Примеры
№ Входные данные Выходные данные
1
AB?
*BC
 ABC
Динамическое программирование
✓ 21✗ 1741 200средняяВойти и решать
Little Difference#27120
Little Lidia likes playing with numbers. Today she has a positive integer n, and she wants to decompose it to the product of positive integers.

Because Lidia is little, she likes to play with numbers with little difference. So, all numbers in decomposition should differ by at most one. And of course, the product of all numbers in the decomposition must be equal to n. She considers two decompositions the same if and only if they have the same number of integers and there is a permutation that transforms the first one to the second one.
Write a program that finds all decompositions, which little Lidia can play with today.

Input
The only line of the input contains a single integer n (1 ≤ n ≤ 1018).

Output
In first line output the number of decompositions of n, or −1 if this number is infinite. If number of decompositions is finite, print all of them one per line. In each line first print number ki of elements in decomposition. Then print ki integers in this decomposition in any order. Don’t forget that decompositions which are different only in order of elements are considered the same.
 
Input Output
12 3
1 12
3 2 3 2
2 4 3
1 -1

In the second example 1 can be represented as product of any number of ones.
Динамическое программирование: последовательностиКонструктив
1 300средняяВойти и решать
Capybara. Канатная дорога#27068
Побывав недавно в лесу, Вася решил построить на деревьях канатную дорогу. Он хочет, чтобы дорога была как можно более длинной, но он плохо помнит высоты деревьев в лесу. К счастью, он уверен, что правильно помнит высоты всех деревьев, кроме, возможно, одного из них.

Известно, что лес состоит из n деревьев, стоящих в ряд и пронумерованных слева направо числами от 1 до n. Высота i-го дерева, по воспоминаниям Васи, равна hi. Канатная дорога длины k должна опираться на k (1 <= k <= n) деревьев i1, i2, . . . , ik (i1 < i2 < . . . < ik), таких что их высота возрастает, то есть, hi1 < hi2 < . . . < hik.
Петя тоже был в лесу, и у него есть q предположений о том, где именно ошибается Вася. Его i-е предположение задаётся числами ai и bi , означающими, что, по мнению Пети, высота дерева
с номером ai на самом деле равна bi . Обратите внимание, Петины предположения независимы между собой.

Ваша задача состоит в том, чтобы для каждого предположения Пети найти максимальную длину канатной дороги, которую можно построить с опорой на эти деревья.
Отметим, что в рамках данной задачи длиной дороги Вася считает количество опорных деревьев в ней.
 
Формат входных данных
Первая строка входных данных содержит два числа n и m (1 <= n, m <= 400 000) — количество деревьев в лесу и количество предположений Пети соответственно.
В следующей строке содержатся n целых чисел hi (1 <= hi <= 109 ) — высоты деревьев по предположению Васи.

Каждая из следующих m строк содержит по два целых числа ai и bi (1 <= ai <= n, 1 <= bi <= 109 ).

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

Ввод Вывод
4 4
1 2 3 4
1 1
1 4
4 3
4 5		 4
3
3
4
4 2
1 3 2 6
3 5
2 4		 4
3
Замечание
Рассмотрим первый пример. Первое Петино предположение совпадает с предположением Васи.
Согласно его второму предположению, высоты деревьев были (4, 2, 3, 4), третьему (1, 2, 3, 3), а по четвёртому предположению — (1, 2, 3, 5).
Динамическое программированиедп
✓ 1✗ 411 300средняяВойти и решать
Вупсень и Пупсень 2#24637
Как вы уже знаете, Вупсень очень любит давать задачи на поиск наибольшей общей подпоследовательности, а Пупсень очень любит давать задачи на поиск наибольшей правильной скобочной подпоследовательности. Лунтик решил обрадовать своих друзей и подарить им на новый год две строки. Конечно же, Вупсень и Пупсень сразу, не посмотрев на строки, захотели дать задачу на поиск наибольшей общей правильной скобочной подпоследовательности, но не тут то было: в этих строках не было скобок. Лунтик понимал, что если Вупсень и Пупсень увидят решения с битсетами, то будут грустить, и весь праздник испортится, поэтому он придумал другую задачу: найдите длину наибольшего общего подпалиндрома.

Подпалиндромом называется такая попоследовательность строки, которая читается справа налево также, как и слева направо.
 
Формат входный данных
В первой строке дана строка s, во второй строке строка t, состоящие из строчных латинских букв. 1 <= |s|, |t| <= 50.
 
Формат выходных данных
Выведите одно целое число n - длину наибольшей общей подпоследовательности, являющейся палиндромом.
 
Примеры
Ввод Вывод
mem
kek
 1
acab
abca
 3
(с) Буков Антон, 11и
Динамическое программирование по подстрокам
✓ 1✗ 31 200средняяВойти и решать
Пустоты в кубе#23588
Жюри составило отчет об учебно-тренировочных сборах по информатике и собирается распечатать его на стандартном листе бумаги. Весь отчет набран одним моноширинным шрифтом, т.е. все символы (включая пробелы) имеют одинаковую ширину. Длина строки при печати этим шрифтом на листе бумаги равна S.
 
Назовем пустотой последовательность пробелов между соседними словами в строке, а также от начала строки до первого слова в ней и от последнего слова в строке до конца строки. Проблема, стоящая перед жюри, состоит в том, что научный руководитель сборов Владимир Михайлович Кирюхин отказывается читать текст, если сумма кубов длин пустот по всем строкам не минимальна. Помогите жюри расположить отчет на листе бумаги так, чтобы В.М. Кирюхин согласился его прочесть и утвердить результаты сборов.
 
Для достижения требуемого расположения текста на бумаге разрешается заменять произвольную пробельную последовательность (т.е. непустую последовательность подряд идущих пробелов или символов перевода строки) любой другой пробельной последовательностью.
 
Входные данные
Первая строка входного файла содержит целое число S (1<=S<=80). 
В последующих строках записан отчет, содержащий не более 500 слов. 
Длина каждой строки отчета не превосходит 250 символов, а длина каждого слова не превос-ходит S.
 
Выходные данные
Вывести в первую строку выходного файла минимально возможную сумму 
кубов пустот по всем строкам. В последующие строки следует вывести 
искомое расположение текста на листе бумаги.
 
Пример входного файла
30
Победители летних учебно-тренировочных сборов по информатике 1997 г.:
Владимир Мартьянов,
Анатолий Пономарев,
Николай Дуров,
Андрей Лопатин.
 
Пример выходного файла
325
     Победители     летних    
учебно-тренировочных сборов по
 информатике 1997 г.: Владимир
Мартьянов, Анатолий Пономарев,
Николай Дуров, Андрей Лопатин.
 
Динамическое программирование: один параметрреализация
✓ 0✗ 11 300средняяВойти и решать
По крышам!#23367
В городе будущего Иннополис еще во всю идет стройка, но уже сейчас построено n зданий. Крышу каждого здания можно представить как прямоугольник со сторонами, параллельными осям координат. Никакие здания не касаются и не пересекаются.

Инна любит гулять по крышам. Она стоит на крыше здания с номером 1 и хочет попасть на крышу здания с номером n.

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

Помогите Инне посчитать, какое минимальное количество раз она должна прыгнуть с одной крыши на другую, чтобы попасть на здание с номером n.

Формат входных данных
В первой строке задано натуральное число n — число зданий в Иннополисе (n<= 105). В следующих n строках заданы крыши зданий. Каждая из этих строк содержит четыре целых числа xi1, yi1, xi2 и yi2 — координаты противоположных вершин прямоугольника, описывающего крышу здания (xi1 < xi2; yi1 < yi2) Гарантируется, что никакие два прямоугольника не имеют общих точек. Все координаты — неотрицательные целые числа и <= 109

Формат выходных данных
Выведите одно целое число — минимальное количество прыжков, которые Инна должна совер- шить, чтобы добраться с крыши здания 1 до крыши здания n. Если же Инна не может добраться до крыши n-го здания, выведите -1.
Ввод Вывод
4
0 0 3 2
1 6 4 8
1 3 4 5
7 7 10 9		 3
3
0 0 3 2
1 3 4 5
7 7 10 9		 -1
Динамическое программированиеДинамическое программирование
✓ 0✗ 71 200средняяВойти и решать
Ведьмак#22027
По приезде Геральда в Каэр-Морхен уже наступила зима. Вокруг стояла тишина, а окна замка приветливо светились в темноте. Редкие факелы создавали теплую и согревающую атмосферу, освещая ровный белый ковер из снега. Среди этой красоты особенно порадовал Геральда отъезд Весемира, ведь теперь можно закатить грандиозную пьянку!
Для этого на кухонный стол достали n кружек. Геральд суетился и переставлял кружки с l по r в позицию i, Ламберт с упоением доливал Ривский эль в кружки с l по r по s литров в каждую, а вот Эскель , пока никто не видит, выпивал или доливал в каждую кружку с l по r столько, чтобы в них осталось ровно по k литров в каждой. Спустя почти час Йеннифер, которой порядком надоела брань Ламберта и Эскеля, спустилась вниз, чтобы узнать причину шума. После небольшой перепалки Йеннифер решила помочь отнести кружки в главную столовую, где бурное веселье ведьмаков не мешало бы ей спать. Но так как кружки очень тяжелые, то она может унести не более l литров. Естественно, она хочет пойти спать как можно быстрее, а значит собирается унести как можно больше эля, но общим весом не более l.

Помогите Йеннифер узнать, какой максимальный вес и количество кружек с таким весом она может унести?

Формат входных данных
Дано число n(1 <= n <= 10^4) количество кружек и q(1 <= q <= 10^4) – количество операция. Далее идет описание операций(1 <= l <= r <= 10^4)
• G l r i - Геральд переставляет кружки с l по r в позицию I (1  <= I <=10^4+1)(вставка отрезка производится перед указанным индексом)
• L l r s - Ламберт доливает в кружки с l по r по s литров (1 <= s <= 10^3)
• E l r k – Эскель выпивает из кружек с l по r так, чтобы в каждой оказалось по k литров (1 <= k <= 10^3)
Затем на новой строке идет число l(1 <= l <= 10^5) – количество литров которые может унести Йеннифер. 
Изначально в кружках по 0 литров.

Формат выходных данных
На первой строке через пробел вывести последовательность кружек после проделанных операций, а на второй строке максимальное количество кружек, которые сможет унести Йеннифер и их общий вес. 
 
Пример входных данных Пример выходных данных
5 7
L 2 5 10
G 1 3 5
L 1 4 3
L 3 3 4
E 2 3 2
E 2 2 4
E 5 5 15
15		 13 4 2 13 15
2 15
 
 
5 6
E 1 1 1
E 2 2 2
E 3 3 3
E 4 4 4
E 5 5 5
G 5 5 1
10		 5 1 2 3 4
4 10
5 8
E 1 1 1
E 2 2 2
E 3 3 3
E 4 4 4
E 5 5 5
G 5 5 1
G 1 1 6
G 1 5 1
10		 1 2 3 4 5
4 10

Пояснения к 1 примеру
1. 0 10 10 10 10
2. 10 0 10 10 10
3. 13 3 13 13 10
4. 13 3 17 13 10
5. 13 2 2 13 10
6. 13 4 2 13 10
7. 13 4 2 13 15
Йеннифер может унести 15 литров. Это значит что она может взять либо одну кружку (15 литров или 13 литров), либо две кружки(4 и 2 литра или 13 и 2 литра). Так как она хочет унести как можно больше кружек, то ответ 2.
Пояснения к 3 примеру
1. 1 0 0 0 0
2. 1 2 0 0 0
3. 1 2 3 0 0
4. 1 2 3 4 0
5. 1 2 3 4 5
6. 5 1 2 3 4
7. 1 2 3 4 5
8. 1 2 3 4 5
Йеннифер может унести 10 литров. Наилучший вариант будет 4 и 3 и 2 и 1 литр. Ответ 4.

(с) Аксенов Владимир 10и
Задача о рюкзакереализация
✓ 1✗ 31 200средняяВойти и решать
Поделиться
Класснуть