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

Вожди известного племени Мумба-Юмба решили придумать новый боевой вопль для своих воинов. При этом они решили, что вопль должен состоять ровно из N букв (всего в алфавите племени M букв). Также, после долгих исследований было выяснено, что если в вопле встречается слово si (слово – это последовательность букв алфавита, не длиннее трех символов), то этот вопль вселяет во врага fi единиц страха. Если в вопль входит несколько слов, то их “страшность” суммируется. Например, если вопль содержит слова si и sj, то вопль вселяет fi+fj единиц страха.

Требуется по заданным N, M, алфавиту и списку слов si составить максимально страшный вопль.

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

В первой строке записано три числа — N, M и К (1 ≤ N ≤ 100, 1 ≤ M ≤ 24, 0 ≤ K ≤ 100), где K — количество страшных слов. В следующей строке записан алфавит — строка из M строчных латинских букв. Далее в K строках записана информация о словах — само слово и через пробел одно число, обозначающее страшность этого слова (1 ≤ fi ≤ 10000).

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

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

Примеры
Входные данные
3 5 4
abcde
abc 10
ab 5
be 7
e 4
Выходные данные
16
abe
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
128 megabytes

Найти количество покрытий прямоугольника 2 * n фигурами в виде дощечек, каждая из которых представляет собой либо квадрат со стороной 1, либо два квадрата (2 * 1), либо “уголок” из трех квадратов:

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

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

Вводится число n(1 ≤ n ≤ 1000).

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

Выведите количество возможных покрытий.

Примеры
Входные данные
2
Выходные данные
11
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
8 megabytes

Новый Мытищинский театр «Фэст» украшен гигантской гирляндой, управляемой компьютером, в которой используются тысячи лампочек. Каждый ряд лампочек в гирлянде управляется набором переключателей, которые контролируются с использованием специальной компьютерной программы. К сожалению, электрики установили неверный набор переключателей, а сегодня вечером состоится открытие театра. Ваша задача — написать программу, которая бы заставила переключатели работать корректно. Ряд лампочек в гирлянде состоит из n лампочек и контролируется n переключателями. Лампочки и переключатели занумерованы слева направо от 1 до n. Каждая лампочка может быть либо включена, либо выключена. Каждый тестовый пример в этой задаче будет содержать начальную и желаемую конечную конфигурации лампочек. Исходно предполагалось, что каждый переключатель будет контролировать одну лампочку. Однако ошибка в электронике привела к тому, что каждый переключатель помимо своей лампочки также изменяет состояние двух (или одной, если основная лампочка находится c краю) соседних с ней. Так, самый левый переключатель (i = 1) изменяет состояние двух самых левых лампочек (1 и 2), а самый правый (i = n) — двух самых правых (n - 1 и n). Каждый из оставшихся переключателей (1 ≤ i ≤ n) изменяет состояние трех лампочек с номерами i - 1, i и i + 1. Исключение составляет единственный случай, когда имеется ровно одна лампочка и один переключатель. В этом случае этот переключатель контролирует эту лампочку. Таким образом, если, к примеру, лампочка 1 включена, а лампочка 2 выключена, то при нажатии на переключатель 1 лампочка 1 выключится, а лампочка 2 включится. Определим минимальную стоимость перехода из одной конфигурации к другой как минимальное количество переключателей, которое требуется нажать, чтобы получить из начальной конфигурации конечную.

Можно представить состояние ряда лампочек как двоичное число, где 0 означает, что лампочка выключена, а 1 — что лампочка включена. Так, в частности, двоичное число 01100 представляет собой ряд из пяти лампочек, среди которых вторая и третья включены, а остальные выключены. Можно превратить эту конфигурацию в конфигурацию 10000, нажав последовательно на переключатели 1, 4 и 5, но дешевле сделать это, просто изменив состояние переключателя 2. Напишите программу, которая определит, на какие переключатели следует нажать, чтобы перевести начальную конфигурацию лампочек в конченую за минимальной стоимость. В некоторых случаях подобное может оказаться невозможным. Отметим, что для компактности представления двоичные числа записываются как десятичные, то есть вместо 01100 и 10000 используются числа 12 и 16 соответственно.

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

Входной файл содержит несколько тестовых примеров. Каждый тестовый пример занимает одну строку. Строка содержит два неотрицательных целых десятичных числа, по крайней мере одно из которых положительно и каждое из которых содержит не более 100 цифр. Двоичная запись первого числа представляет собой начальную конфигурацию, а второго — конечную. Чтобы избежать проблем с ведущими нулями, будем предполагать, что первая лампочка либо в начальной, либо в конченой конфигурации включена. Во входном файле не будет пробелов в начале или конце строки, числа записаны без ведущих нулей и разделены ровно одним пробелом. Последняя строка входного файла содержит два нуля.

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

Для каждого тестового примера выведите в выходной файл одну строку. Она должна содержать номер тестового примера и десятичное число, двоичное представление которого кодирует набор переключателей, которые требуется нажать, чтобы из начальной конфигурации получить конечную. В двоичном представлении этого числа самый правый (наименее значимый) бит должен соответствовать переключателю с номером n, 1 означает, что переключатель следует нажать, а 0 — что нет. Если решения не существует, то вместо этого числа следует вывести слово “impossible”. Если имеется более одного решения, выведите то, которое представляется меньшим десятичным числом. Разделяйте вывод для тестовых примеров пустой строкой. Используйте формат, приведенный в примере.

Примеры
Входные данные
12 16
1 1
3 0
30 5
7038312 7427958190
4253404109 657546225
0 0
Выходные данные
Case Number 1: 8

Case Number 2: 0

Case Number 3: 1

Case Number 4: 10

Case Number 5: 2805591535

Case Number 6: impossible

ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

Комната имеет прямоугольную форму размером M × N (1 ≤ M ≤ 9, 1 ≤ N ≤ 9) . Необходимо уложить его паркетом. Есть деревяшки двух форм:

  • прямоугольники (2 × 1)
  • уголки (квадрат 2 × 2 без одного куска 1 × 1 )

Вы должны найти X — количество способов покрыть пол паркетом (не должно остаться пустых мест; части не должны накладываться друг на друга и выходить за границу комнаты).

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

В первой строке входного файла расположены через пробел два натуральных числа: N и M .

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

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

Примеры
Входные данные
2 3
Выходные данные
5
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Город Загреб решил построить новую парковку. Для этого было решено использовать прямоугольный участок земли, который можно представить в виде матрицы с $N$ строками и $M$ столбцами. Чтобы привлечь гостей и увеличить доходы, мэр решил разместить фонтаны на заранее определенных участках земли. Остальные же клетки будут преобразованы в парковочные места и дороги. Машины могут двигаться по парковке, перемещаясь в соседнее поле в одном из четырех направлений (север, юг, восток или запад). При этом парковочные места должны быть выбраны так, чтобы любая припаркованная машина могла выехать из парковки, то есть иметь возможность попасть в левую верхнюю клетку, не врезаясь в другие припаркованные машины.

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

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

Первая строка содержит натуральные числа $N$ и $M$ $(1 \le N \le 6, 1 \le M \le 100)$ – количество строк и столбцов участка.

Следующие $N$ строк содержат $M$ символов, каждый из которых описывает состояние соответствующей клетки – знак «x» обозначает клетку, на которой будет построен фонтан, другие клетки помечены знаком «.» и будут преобразованы в парковку.

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

На единственной строке выведите максимальное количество парковочных мест.

Система оценки

В этой задаче 6 подгрупп.

  • (10 баллов) Ограничения: $N, M \le 4$
  • (10 баллов) Ограничения: $N = 2$
  • (20 баллов) Ограничения: $N = 3$
  • (20 баллов) Ограничения: $N = 4$
  • (20 баллов) Ограничения: $N = 5$
  • (20 баллов) Ограничения: $N = 6$

Примечание

Поле в первой строке и первом столбце является входом на парковку и не предназначено для парковки.

Примеры
Входные данные
3 3
...
.x.
...
Выходные данные
2
Входные данные
3 3
...
..x
...
Выходные данные
4
Входные данные
3 6
.x..x.
..x.x.
......
Выходные данные
3
Входные данные
4 5
....x
....x
..x..
.x..x
Выходные данные
7

Страница: << 1 2 3 4 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест