#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

#409

Максимальная сумма

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

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

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

Сегодня на страницах газеты «Математический досуг» была опубликована необычная математическая головоломка. Одна из страниц газеты полностью занята прямоугольной таблицей, состоящей из m строк и n столбцов. В каждой ячейке таблицы записано некоторое целое число.

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

Безуспешно потратив несколько часов на решение головоломки, Саша решил написать программу, которая сделала бы это за него. Но и тут его постигла неудача. Теперь ему ничего не остается, как обратиться за помощью к вам.

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

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

В первой строке вводятся два целых числа $m$ и $n$ ($2 \le m, n \le 300$). Далее следует описание таблицы – $m$ строк, каждая из которых содержит по $n$ целых чисел $a_{i, j}$ ($-10^4 \le a_{i,j} \le 10^4$).

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

В первой строке выведите целое число $s$ – максимальную сумму чисел на границе искомого прямоугольника. Во второй строке выведите четыре натуральных числа: $x_1$, $y_1$, $x_2$, $y_2$ – координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь $x$ – номер строки, а $y$ – номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.

Примеры

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

2 3
1 1 1
1 1 1

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

6
1 1 2 3

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

5 4
9 -2 -1 3
-10 -5 1 -4
1 -1 2 -2
3 0 0 -1
2 2 -1 2

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

8
3 1 5 3

#544

Космический мусорщик

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

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

Вызов функции осуществляется с одним числовым параметром. Функция прибавляет один к счетчику и вызывает заданный набор функций с параметром, на 1 меньшим. При параметре 0 функция прекращает работу. Требуется вывести значение счетчика.

В околоземном космическом пространстве накопилось много мусора, поэтому ученые сконструировали специальный аппарат - ловушку для космического мусора. Для того, чтобы хорошо собирать мусор, этот аппарат должен двигаться по достаточно сложной траектории, сжигая собранный по пути мусор. Ловушка может передвигаться в пространстве по 6 направлениям: на север ($N$), на юг ($S$), на запад ($W$), на восток ($E$), вверх ($U$) и вниз ($D$). Движением ловушки управляет процессор. Программа движения задается шестью правилами движения, которые соответствуют каждому из указанных направлений. Каждое такое правило представляет собой строку символов из множества {$N$, $S$, $W$, $E$, $U$, $D$}.

Команда ловушки есть пара из символа направления и параметра - целого положительного числа $M$. При исполнении такой команды ловушка в соответствии со своей программой выполняет следующее. Если параметр больше 1, то она перемещается на один метр в направлении, которое указано в команде, а затем последовательно выполняет команды, заданные правилом для данного направления, с параметром меньше на 1. Если же параметр равен 1, то просто перемещается на один метр в указанном направлении.

Пусть, например, заданы следующие правила:

Тогда при выполнении команды $S$(3) мусорщик выполнит следующие действия:

1) переместится на 1 метр в направлении $S$
2) выполнит последовательно команды $N$(2), $U$(2), $S$(2), $D$(2), $D$(2), $U$(2), $S$(2), $E$(2).
Если далее проанализировать действия мусорщика при выполнении команд из пункта 2, получим, что в целом он совершит следующие перемещения:

SNNUUSNUSDDUSEDWEDDWEDUUSNUSDDUSEEПо заданной команде определите, какое общее количество перемещений на один метр совершит ловушка при выполнении заданной команды. В приведенном примере это количество равно 34.

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

Первые шесть строк входных данных задают правила для команд с направлением $N$, $S$, $W$, $E$, $U$ и $D$ соответственно. Каждая строка содержит не более 100 символов (и может быть пустой). Следующая строка содержит команду ловушки: сначала символ из множества {$N$, $S$, $W$, $E$, $U$, $D$}, затем пробел и параметр команды - целое положительное число, не превышающее 100.

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

Выведите единственное число - количество перемещений, которое совершит ловушка. Гарантируется, что ответ не превышает $10^9$.

Примеры

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

N
NUSDDUSE
UEWWD

U
WED
S 3

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

#545

Две стены

Темы: [Задача о рюкзаке]

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

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

У Пети есть набор из $N$ кирпичиков. Каждый кирпичик полностью окрашен в один из $K$ цветов, $i$-й кирпичик имеет размер 1×1×$L_i$. Петя знает, что он может построить из всех кирпичиков прямоугольную стену толщиной 1 и высотой $K$, причем первый горизонтальный слой кирпичиков в стене будет первого цвета, второй - второго и т. д. Теперь Петя хочет узнать, может ли он из своего набора построить две прямоугольные стены, обладающие тем же свойством. Помогите ему выяснить это.

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

В первой строке входных данных задаются числа $N$ и $K$ (1 <= $N$ <= 5000, 1 <= $K$ <= 100). Следующие $N$ строк содержат описание Петиных кирпичиков: сначала длина Li, затем номер цвета $C_i$ (1 <= $L_i$ <= 100, 1 <= $C_i$ <= $K$). Известно, что у Пети не более 50 кирпичиков каждого цвета.

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

Выведите в первой строке YES, если Петя сможет построить из всех своих кирпичиков две прямоугольные стены высоты $K$, $j$-й слой кирпичиков в каждой из которых будет $j$-го цвета, и NO в противном случае. В случае положительного ответа, выведите во второй строке в произвольном порядке номера кирпичиков, из которых следует построить первую стену (кирпичики нумеруются в том порядке, в котором они заданы во входных данных, начиная с 1). Если решений несколько, можно выдать любое из них.

Примеры

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

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

YES
1

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

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

YES
1 2

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

2 2
1 1
1 2

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

NO

#572

Пузырьки 1D

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

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

Задан одномерный массив "пузырьков", каждый из которых может быть одного из четырех цветов. Можно уничтожить группу подряд идущих пузырьков одинакового цвета и получить за это $K^2$ очков (K - количество пузырьков). Требуется уничтожить все пузырьки и подсчитать максимальную сумму очков.

Сережа - большой любитель игр на сотовом телефоне. Недавно он скачал из интернета новую игру "Пузырьки 1D". Опишем правила игры.

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

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

Например, ниже на рисунке показана позиция, содержащая 10 пузырьков. В ней четыре группы, содержащие 3, 2, 4 и 1 пузырек, соответственно. Если взорвать группу, содержащую четыре пузырька, то игрок получит 16 очков, и верхние 5 пузырьков опустятся вниз. В получившейся позиции 6 пузырьков, и две группы по 3 пузырька в каждой.

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

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

На вход программы поступает одна строка, состоящая из букв "R", "G", "B и "Y", описывающая начальную позицию. Буквы задают цвета пузырьков в порядке просмотра сверху вниз ("R" означает красный пузырек, "G" – зеленый, "B" – синий, а "Y" – желтый). В заданной позиции не менее двух и не более 100 пузырьков.

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

Выведите одно число – максимальное количество очков, которое сможет заработать Сережа. Если уничтожить все пузырьки невозможно, выведите 0.

Пояснения

В первом примере следует действовать следующим образом: сначала надо взорвать группу из четырех красных пузырьков, получив 16 очков. Затем надо взорвать в любом порядке получившиеся две группы по 3 пузырька, получив по 9 очков за каждую.

Примеры

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

RRRGGRRRRG

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

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

RB

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