#77

Путевые строки

Темы: [Динамическое программирование: последовательности] [Динамика по подмножествам]

Рассмотрим ориентированный граф G, имеющий n вершин, пронумерованных натуральными числами от 1 до n. В графе G возможно наличие нескольких дуг между одной и той же парой вершин, а также дуг, ведущих из вершины в нее саму. Каждая дуга графа помечена некоторой буквой латинского алфавита. Каждому пути в графе G можно поставить в соответствии строку, состоящую из букв, написанных на последовательно проходимых в соответствии с этим путем дугах. Эта строка называется путевой меткой пути. Назовем строку S путевой строкой графа G, если в нем существует путь, путевая метка которого равна S.

Ваша задача посчитать остаток от деления на 1 000 000 количества путевых строк графа G, состоящих ровно из L символов.

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

В первой строке входных данных записаны целые числа n, m, L (1 ≤ n ≤ 10, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 100), равные количеству вершин и ребер графа G, а также длине путевых строк, которые нужно искать. Следующие m строк задают дуги графа G. Каждая из этих строк содержит два натуральных числа a, b (1 ≤ a, b ≤ n) и маленькую латинскую букву c, что означает наличие дуги из вершины a в вершину b, помеченной символом c. Элементы каждой строки отделены друг от друга пробелами.

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

Единственная строка выходных данных должна содержать одно число, равное остатку от деления количества путевых строк длины L в графе G на 1 000 000.

Примеры

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

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

#78

Прямоугольники

Темы: [Динамическое программирование на таблицах] [Динамическое программирование по профилю]

Дан прямоугольник N x M, состоящий из квадратиков 1 x 1. Некоторые квадратики вырезали. Надо найти наименьшее количество прямоугольников, на которое можно разрезать оставшуюся фигуру.

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

В первой строке входных данных заданы числа N и M, (1 ≤ N, M ≤ 10). Далее следует N строк. В (i+1)-ой содержится M чисел; j-е число равно 1, если клетку на i-й строке и в j-м столбце вырезали из доски, 0 – если оставили.

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

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

Примеры

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

2 2 
0 0
1 0

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

#79

Арбузная грядка

Темы: [Динамическое программирование на таблицах]

Ограничение по времени: 3 секунды
Ограничение по памяти: 64 мегабайта

На этот раз Вася увлекся выращиванием арбузов. Его огород имеет форму прямоугольника $N \times M$ метров, разделенного на одинаковые ячейки размером $1 \times 1$ метр, в каждой из которых растет по арбузу. Как-то раз он решил осмотреть некоторые из них, начав в левом верхнем углу, пройдясь по огороду и вернувшись обратно. Ячейки, оказавшиеся внутри цикла, считаются осмотренными, остальные – не осмотренными. По некоторым банальным соображениям Вася не ходит по грядкам, а только лишь по специальным дорожкам, расположенным на границах ячеек с арбузами. Вдобавок, он хочет, чтобы его путь получился без самопересечений. К счастью, дорожки достаточно широкие для того, чтобы гулять по ним много раз, не считая это за самопересечение (см. рисунки к примерам).

Ваша задача – узнать, за какое минимальное время Васе удастся обойти ровно i арбузов. Можно считать, что он двигается равномерно со скоростью 1 метр в секунду.

Формат входных данных

В первой строке входных данных содержатся два числа $N, M (1 \le N, M \le 50)$. В следующих N строках идет описание огорода. В (i + 1)-й строке содержатся M символов. Символ "I" на j-й позиции означает, что Вася хочет осмотреть арбуз, расположенный в i-й строке и j-м столбце огорода; символ " ." означает, что ему не важно, что происходит в соответствующей ячейке; символ "X" означает, что он не хочет осматривать это растение. Других символов в строке нет.

Гарантируется, что суммарное количество символов "I" и "X" не превосходит 10, и присутствует хотя бы один символ "I".

Формат выходных данных

Выведите ровно K чисел, разделенных пробелами, где K – количество арбузов, которые Вася хочет осмотреть (количество символов "I" во входном файле). Число номер i должно быть равно минимальному времени, за которое он успеет осмотреть ровно i арбузов, соответствующих символам "I".

Не забудьте учесть, что арбузы, помеченные ".", могут быть осмотрены или нет, но арбузы "X" Вася осматривать не хочет ни в коем случае.

Примеры

Входные данные	Выходные данные
1 1 I	4
2 2 XX XI	8
3 3 III IXI III	4 6 8 10 12 14 16 18
3 3 X. I .I. I..	8 10 14
1 10 IIXIIXIXII	4 6 12 14 20 26 28

#191

Шахматный детектив

Темы: [Динамическое программирование: два параметра] [Перебор с отсечением]

Источники: [ Командные олимпиады, ВКОШП, 2006, Задача A ]

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

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

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

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

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

Шахматная доска – это квадрат, разбитый на x² (для некоторого x) равных квадратов – полей. Стороны полей параллельны сторонам изображения. Длина стороны каждого поля шахматной доски выражается целым числом пикселей. Все пиксели, принадлежащие одному полю, покрашены в один и тот же цвет – черный или белый. При этом соседние поля (поля, имеющие общую сторону) покрашены в различные цвета.

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

В первой строке вводятся два целых числа: m и n – размеры фрагмента фотографии в пикселях ( 1 $le$ m, n $le$ 250).

Следующие m строк содержат по n символов каждая, j-й символ i-й строки соответствует пикселю с координатами (i, j). Символ «.» (точка) означает белый пиксель, символ «*» – черный, символ «?» – серый.

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

Если заданный фрагмент фотографии может быть изображением части шахматной доски, выведите слово «YES». После этого выведите m строк по n символов в каждой – изображение соответствующей части шахматной доски в том же формате, что и во входных данных, только серые пиксели должны быть заменены на белые или черные. Если решений несколько, выведите любое.

В противном случае программа должна вывести слово «NO».

Примеры

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

4 5
*.?.?
.***.
.*?*.
.*?*.

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

YES
*...*
.***.
.***.
.***.

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

4 5
..?..
.***.
.*?*.
.*?*.

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

NO

#204

НОП

Темы: [Динамическое программирование: последовательности]

Даны две последовательности, требуется найти длину их наибольшей общей подпоследовательности.

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

В первой строке входных данных содержится число N – длина первой последовательности (1 ≤ N ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

В третьей строке записано число M – длина второй последовательности (1 ≤ M ≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

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

Требуется вывести одно число – длину наибольшей общей подпоследовательности двух данных последовательностей или 0, если такой подпоследовательности нет.

Примеры

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

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