Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование по профилю
---> 20 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 >> Отображать по:
#1032
Узор
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

В комнате решили сделать паркетный пол. Причем есть задумка выложить на полу некоторый узор.

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

Существует несколько форм паркетных плиток:

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

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

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

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

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

<форма> <стоимость> <окраска>

<Форма> — это число от 1 до 4, описывающее форму плитки (см. рисунок выше)

<Стоимость> — это натуральное число, не превосходящее 10000, задающее стоимость одной плитки такого типа

<Окраска> — это от одного до трех чисел 0 или 1. Количество чисел совпадает с количеством квадратиков, из которых состоит плитка. Числа задают цвета квадратиков плитки в том порядке, в каком квадратики пронумерованы на рисунке.

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

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

Примеры
Входные данные
4 3 3
2 2 2
2 0 0
2 1 2
2 2 2
2 10 0 0
1 5 1
4 6 0 0 1
Выходные данные
15
#1805
Ящички-2
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В недавно открытой раздевалке школы «Интеллектуал» решено поставить такие же шкафчики, как и в уже давно используемых раздевалках, но более новой модификации — состоящие из \(H*W\) ячеек. Напомним, что в каждую ячейку можно поставить ящичек, чтобы хранить в нём свои вещи. Однако новый директор школы запретил ученикам хранить свои вещи вне ящичков, поэтому тем, кому ящички не достались, приходится просить кого-то из владельцев соседних четырёх (или менее, если ячейка находится на границе) ячеек похранить свои вещи у себя. Если же ни у кого из соседей по ячейкам нет ящичков, этот ученик жалуется в администрацию.

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

Количество учеников равно количеству ячеек.

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

В единственной строке входного файла содержатся два натуральных числа \(H\) и \(W\) (1 \(\le\) \(H\), \(W\) \(\le\) 8).

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

Выведите единственное натуральное число — искомое количество способов.

Примеры
Входные данные
2 2
Выходные данные
11
#1849
Плитки
  
Источники: [ Командные олимпиады, ВКОШП, 1999, Задача D ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1×1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:


К

К

К

С

З

К

К

З

К

С


(Буквой К обозначена красная плитка, С – синяя, З – зеленая)

После этого Петя заполняет следующую таблицу:

красный

синий

зеленый

красный

Y

Y

Y

синий

Y

N

Y

зеленый

Y

Y

N


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

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

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

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


С

К

З

К

К

З

С

К

К

К


не совпадает с полоской, приведенной в начале условия.)

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

Первая строка входного файла содержит число N. (1 N 100). Следующие три строки входного файла, содержащие по три символа из набора {"Y", "N"}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична.

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

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

Примеры

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

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

10

YYY

YNY

YYN

4596

3

YYY

YYY

YYY

0


#1938
ЕГЭ
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

С целью упрощения ЕГЭ по литературе, было решено оставить в нем вопросы только с ответами «да» или «нет». Бланк ответов представляет клетчатое поле из \(N\) строк и \(M\) столбцов, в котором каждая клеточка соответствует своему вопросу. Ученику необходимо один раз перечеркнуть по диагонали те клеточки, которые, по его мнению, соответствуют вопросам с ответом «нет» (перечеркивать можно по любой из двух диагоналей). При этом во избежание ошибок при сканировании, никакие две диагонали не должны "сливаться", то есть иметь общий конец.

Авторам варианта необходимо знать, какое наибольшее количество вопросов с ответом «нет» можно вставить в вариант, чтобы бланк с правильными ответами мог быть верно распознан компьютером.

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

Вводится два натуральных числа – количество строк \(N\) и количество столбцов \(M\). Количество вопросов в варианте не превосходит 100, то есть \(1 ≤ N ∙ M ≤ 100\).

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

В первую строку выведите одно число — максимальное количество вопросов с ответом «нет», которое можно включить в вариант. В следующие N строк выведите по M символов – пример такого бланка с правильными ответами, верно распознаваемый компьютером. Никакие две диагонали не должны иметь общих концов. Руководствуйтесь следующими обозначениями: . (точка) — пустая клетка, соответствующая ответу «да»; / или \ — перечеркнутые по диагонали справа налево или слева направо клетки, соответствующие ответу «нет». Если существует несколько вариантов заполнения бланка, выведите любой.

Примеры
Входные данные
1 1
Выходные данные
1
/
Входные данные
2 1
Выходные данные
2
/
/
Входные данные
3 3
Выходные данные
6
///
../
\\.
#3184
Космические исследования
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Отделу космических исследований поступило задание сфотографировать из космоса \(n\) объектов в заданной области. Область имеет форму квадрата размером \(50\times 50\) километров. Если разделить ее на квадраты размером \(1\times 1\) километр, то интересующие отдел объекты окажутся в центрах некоторых единичных квадратов.

Введем систему координат, направив ось OX с запада на восток и ось OY с юга на север. Тогда каждому единичному квадрату будут сопоставлены координаты в диапазоне от 1 до 50, как показано на рисунке ниже.

Для космической съемки используется специальный фотоаппарат высокого разрешения, установленный на космическом спутнике. Фотоаппарат может делать снимки квадратных участков земной поверхности размером \(k\times k\) километров. Исходно аппарат наведен на юго-западный угол заданной области, то есть, если сделать снимок, на нем будут видны единичные квадраты с координатами \(x\) и \(y\) от \(1\) до \(k\) километров.

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

Руководство отдела заинтересовалось вопросом: за какое минимальное количество дней можно сделать снимки всех объектов заданной области.

Требуется написать программу, которая по заданному расположению объектов и размеру снимка \(k\) определит минимальное время, за которое можно сделать снимки всех объектов заданной области.

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

Первая строка входного файла содержит два целых числа: \(n\) и \(k\) (\(1 \le n \le 1000\), \(1 \le k \le 5\)).

Следующие \(n\) строк содержат по два целых числа: \(x_i\) и \(y_i\) — координаты объектов в заданной области (\(1 \le x_i, y_i \le 50\)).

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

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

Примечание

В первом примере возможна следующая последовательность действий: сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок, 9 раз сместиться на запад, сместиться на север, сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок. Всего требуется 30 перемещений участка съемки.

Во втором примере объекты расположены там же, но размер снимка больше, поэтому можно действовать так: сделать снимок, сместиться на север, сделать снимок, 8 раз сместиться на восток, сделать снимок, сместиться на север, сделать снимок. Всего требуется лишь 10 перемещений участка съемки.

В третьем примере перемещать участок съемки не требуется, можно просто сделать снимок.

Четвертый пример соответствует приведенному выше рисунку.

Правильные решения для тестов, в которых \(k = 1\), будут оцениваться в 30 баллов.

Правильные решения для тестов, в которых \(k \gt 1\) и \(1 \lt n \le 15\), будут оцениваться так же в 30 баллов.

Примеры
Входные данные
4 1
1 1
10 2
1 3
10 4
Выходные данные
30
Входные данные
4 2
1 1
10 2
1 3
10 4
Выходные данные
10
Входные данные
1 1
1 1
Выходные данные
0
Входные данные
3 3
3 3
3 6
6 3
Выходные данные
7
Страница: << 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест