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

Билл пытается компактно представить последовательности прописных символов от 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.

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

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

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

Компания, в которой работает Алексей покупает кабель только в одном специализированном магазине. В магазине продается кабель пятой и шестой категорий по цене P5 и P6 рублей за метр. При этом в наличии имеется только Q5 метров кабеля пятой категории и Q6 метров кабеля шестой категории.

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

Входные данные

В первой строке входного файла содержится число N — количество квартир, которые необходимо соединить и M — количество возможных соединений (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10 000).

Следующие M строк содержат описание возможных соединений. Каждое описание состоит из трех чисел A, B и L — где A и B задают номера квартир, а L — длина соединения между ними (1 ≤ L ≤ 100). Квартиры занумерованы от 1 до N.

Последняя строка входного файла содержит числа P5, Q5, P6, Q6 – цену и количество кабеля пятой и шестой категории соответственно (1 ≤ P, Q ≤ 10 000) .

Выходные данные

Если все квартиры можно соединить в сеть, то следует вывести N строк, описывающих план сети. Первая строка должна содержать стоимость прокладки сети. Следующие N-1 строк должны содержать описание соединений, представленных двумя числами каждое: A_i и C_i, где A_i — номер соединения в списке возможных соединений (от 1 до M), а C_i задает категорию кабеля и может принимать значения 5 или 6. Если планов несколько — выведите любой из них.

Если все квартиры соединить невозможно выведите слово Impossible.

На поле NxM клеток (N строк и M столбцов) положили K прямоугольников один поверх другого в случайном порядке. Длины сторон прямоугольников выражаются целым числом клеток. Прямоугольники не выходят за границы поля. Границы прямоугольников совпадают с границами клеток поля.

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

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

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

0	2	2	2	2
0	2	2	2	2
1	1	2	2	2
1	1	0	0	0

Входные данные
В первой строке входного файла записаны целые числа N, M, K (1≤N≤200, 1≤M≤200, 1≤K≤255). Далее следует N строк по M чисел в каждой — содержимое таблицы. Все числа в таблице целые, находятся в диапазоне от 0 до K включительно.

Выходные данные
В выходной файл необходимо выдать K строк. Каждая строка должна описывать соответствующий ее номеру прямоугольник четырьмя числами R C H W (R и C должны описывать координаты левого нижнего угла прямоугольника, а H и W — координаты правого верхнего угла). Числа должны разделяться пробелом.

Оси координат устроены следующим образом: начало координат находится в нижнем левом углу поля, а оси координат направлены вдоль сторон поля (ось Ox — вдоль нижней стороны, а ось Oy — вдоль левой стороны). Клетки поля имеют размер 1x1. Таким образом, координаты левого нижнего угла поля — (0,0), правого верхнего — (M,N). Заметьте, что вы должны вывести координаты углов прямоугольников (как точек) в этой системе координат, а не координаты угловых клеток, покрытых прямоугольниками.

Анаграммер — специальное устройство для получения из слова его анаграмм (то есть слов, записанных теми же буквами, но в другом порядке). Это устройство умеет выполнять 2 операции:

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

Стек — это хранилище данных, которое работает по принципу "первый пришел — последний ушел". Стек можно представить себе в виде пирамидки. Когда мы добавляем букву в стек, это соответствует тому, что на стержень пирамидки сверху мы надеваем кольцо, на котором написана соответствующая буква. Когда берем букву из стека, то это соответствует тому, что мы снимаем со стержня верхнее кольцо, и смотрим, какая буква на нем написана.

Например, слово TROT в слово TORT может быть преобразовано анаграммером двумя различными последовательностями операций: 11112222 или 12112212.

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

Входные данные
Первая строка входного файла содержит исходное слово, а вторая — слово, которое необходимо получить. Слова состоят только из заглавных латинских букв и имеют длину не более 50 символов. Оба слова имеют одинаковую длину. В этих строках не содержится пробелов.

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

Если это количество не превышает 1000, то в последующих строках должны содержаться сами последовательности. Каждая последовательность должна быть выведена на отдельной строке, и состоять из цифр 1 и 2 (указывающих порядок выполнения операций), выведенных без пробелов.

В спортзале размером NxM метров построили современный аттракцион под названием "Левый лабиринт". Для этого на полу спортзала с интервалом в 1 метр начертили линии, параллельные стенам спортзала. Таким образом, спортзал разбили на NxM клеток. Дальше некоторые из этих клеток покрасили в черный цвет.

Аттракцион заключается в том, что участника ставят в некоторой клетке спортзала и просят как можно быстрее добежать до некоторой другой клетки. При этом накладываются следующие условия:

• Участнику запрещено ходить по черным клеткам.
• Придя в какую-то клетку, участник может пойти либо прямо, либо налево, либо направо (если в соответствующем направлении клетка не покрашена в черный цвет): ходить назад, а также ходить по диагонали запрещается.
• За все время пути участнику разрешается повернуть направо (то есть пойти из текущей клетки направо относительно того, откуда он пришел в данную клетку) не более K раз.
• В начальной клетке участник может встать лицом в ту сторону, в какую ему захочется. С какой стороны участник прибежит в конечную клетку также не важно.

Известно, что на то, чтобы перебежать из клетки в соседнюю, участник тратит ровно 1 секунду. Требуется вычислить минимальное время, за которое участник сможет достичь конечной клетки.

Входные данные
Во входном файле сначала записано число K — количество разрешенных поворотов направо (целое число из диапазона от 0 до 5), затем записаны числа N и M, задающие размеры спортзала — натуральные числа, не превышающие 20. Далее записано N строк по M чисел в каждой. Число 0 обозначает непокрашенную клетку, число 1 — покрашенную, число 2 — клетку, откуда стартует участник и число 3 — клетку, куда нужно добежать (клетки, помеченные 2 и 3 являются непокрашенными). В лабиринте всегда есть ровно одна начальная клетка и ровно одна клетка, в которую нужно попасть.

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

По случаю введения больших новогодних каникул устраивается великий праздничный бал-маскарад. До праздника остались считанные дни, поэтому срочно нужны костюмы для участников. Для пошивки костюмов требуется L метров ткани. Ткань продается в N магазинах, в которых предоставляются скидки оптовым покупателям. В магазинах можно купить только целое число метров ткани. Реклама магазина номер i гласит "Мы с радостью продадим Вам метр ткани за P_i бурлей, однако если Вы купите не менее R_i метров, то получите прекрасную скидку — каждый купленный метр обойдется Вам всего в Q_i бурлей". Чтобы воплотить в жизнь лозунг "экономика страны должна быть экономной", правительство решило потратить на закупку ткани для костюмов минимальное количество бурлей из государственной казны. При этом ткани можно купить больше, чем нужно, если так окажется дешевле. Ответственный за покупку ткани позвонил в каждый магазин и узнал, что:

1) реклама каждого магазина содержит правдивую информацию о ценах и скидках;

2) магазин номер i готов продать ему не более F_i метров ткани.

Ответственный за покупку очень устал от проделанной работы и поэтому поставленную перед ним задачу «закупить ткань за минимальные деньги» переложил на своих помощников. Напишите программу, которая определит, сколько ткани нужно купить в каждом из магазинов так, чтобы суммарные затраты были минимальны.

Входные данные
В первой строке записаны два целых числа N и L (1≤N≤100, 0≤L≤100). В каждой из последующих N строк находится описание магазина номер i — 4 целых числа P_i, R_i, Q_i, F_i (1≤Q_i≤P_i≤1000, 1≤R_i≤100, 0≤F_i≤100).

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

Во второй строке выведите N чисел, разделенных пробелами, где i-ое число определяет количество метров ткани, которое нужно купить в i-ом магазине. Если в i-ом магазине ткань покупаться не будет, то на i-ом месте должно стоять число 0. Если вариантов покупки несколько, выведите любой из них.

Если ткани в магазинах недостаточно для пошивки костюмов, выходной файл должен содержать единственное число -1.

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

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

Входные данные
Вводятся два числа N и M — размеры таблицы (1≤N≤20, 1≤M≤20). Затем идет N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).

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

Дизайн-студия Артемия Индюкова получила заказ на разработку очень пафосного лифта для нового небоскреба. За работу взялся сам Артемий, отличающейся, кстати, редкой неадекватностью. У него есть идея-фикс: для управления лифтом достаточно четырех кнопок. Кнопки должны быть следующие:
- Поднятся на A этажей вверх
- Поднятся на B этажей вверх
- Поднятся на C этажей вверх
- Спустится на первый этаж
Изначально лифт находится на первом этаже. Пассажир лифта использует первые три кнопки чтобы попасть на тот этаж, на который он хочет. Если пассажир пытается подняться вверх на A, B или C этажей, а такого этажа в здании не существует (т.е. пассажир хочет подняться выше N-го, последнего этажа), то лифт никуда не едет.
Заказчики проекта оказались с юмором и вместе с отказом от футуристичного дизайна решили оценить адекватность Артемия по шкале от 1 до N. Оценка адеватности равна количеству этажей, на которые можно попасть с первого с помощью такого лифта. Помогите им в этом.

Входные данные
Первая строка содержит число N – высоту небоскреба (1 <= N <= 500 000).

Вторая строка содержит три числа A, B и C, задающие параметры кнопок (1 <= A, B, C <= 100 000).

Выходные данные
Выведите единственное число — оценку адекватности Артемия Индюкова.

Бегемот – это шахматная фигура, которая живет на доске размером 100x100 клеток. За один ход бегемот перемещается на n клеток по горизонтали или вертикали и на m клеток в перпендикулярном направлении. Например, шахматный конь – это бегемотик, у которого n=2, m=1 (или наоборот). Раскрасьте доску, на которой живет бегемот, в два цвета (каждую клетку – в один из двух цветов), так чтобы любой ход из любой клетки приводил бегемота в клетку другого цвета.

Входные данные
Вводятся два натуральных числа n и m, не превосходящие 99.

Выходные данные
Выведите 100 строк по 100 цифр – 1 или 0, обозначающих клетки разного цвета (через пробел).

Поверхность Земли в горной местности можно представить в виде ломаной линии. Вершины ломаной расположены в точках (x₁, y₁), (x₂, y₂),…,(x_N, y_N), при этом x_i<x_i+1.

Обычный горный маг находится в точке (x₁, y₁) и хочет попасть в точку (x_N, y_N). При этом он может перемещаться только пешком. Он может ходить по поверхности Земли (т.е. вдоль ломаной). А может сотворить в воздухе мост и пройти по нему. Мост может соединять две вершины ломаной: мост не может начинаться и заканчиваться не в вершине ломаной, и мост не может проходить под землей (в том числе не может быть туннелем в горе), но мост может каким-то своим участком проходить по поверхности земли. Длина моста не может быть больше R. Суммарно маг может построить не более K мостов.

Какое наименьшее расстояние придется пройти магу, чтобы оказаться в точке (x_N, y_N).

Входные данные
Вводится сначала натуральное число N (2≤N≤100). Затем водится натуральное число K (1≤K≤100) — максимальное количество мостов. Далее вводится целое число R (0≤R≤10000) — максимальная возможная длина моста. Далее вводятся координаты (x₁, y₁), (x₂, y₂),…,(x_N, y_N). Все координаты – целые числа, не превышающие по модулю 10000, для всех i от 1 до N–1: x_i<x_i+1.

Выходные данные
Выведите одно число — минимальную длину пути, которую придется пройти магу (как по земле, так и по мостам). Ответ выведите не менее чем с 5 цифрами после десятичной точки.

Определим правильные скобочные выражения так:

Пустое выражение - правильное.
Если выражение 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.

Выходные данные
Вывести одно целое число - минимально возможное число очков.