Тема:
Информатика
>>
Алгоритмы
>>
Динамическое программирование
>>
Динамическое программирование: классические задачи
Фильтр
Выбрано 4 задачи Убрать все задачи
Сколькими способами можно сделать трёхцветный флаг с горизонтальными полосами одинаковой ширины, если имеется материя шести различных цветов?
РешениеКвадрат 4 × 4 называется магическим, если в его клетках встречаются все числа от 1 до 16, а суммы чисел в столбцах, строках и двух диагоналях равны между собой. Шестиклассник Сеня начал составлять магический квадрат и поставил в какую-то клетку число 1. Его младший брат Лёня решил ему помочь и поставил числа 2 и 3 в клетки, соседние по стороне с числом 1. Сможет ли Сеня после такой помощи составить магический квадрат?
РешениеПеречислить все последовательности длины 2n, составленные из n единиц и n минус единиц, у которых сумма любого начального отрезка неотрицательна, --е число минус единиц в нём не превосходит числа единиц. (Число таких последовательностей называют числом Каталана)
РешениеУ Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1 * 1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:
| К | К | К | С | З | К | К | З | К | С |
(буквой К обозначена красная плитка, С — синяя, З — зеленая).
После этого Петя заполняет следующую таблицу:
| Красный | Синий | Зеленый | |
| Красный | Y | Y | Y |
| Синий | Y | N | Y |
| Зеленый | Y | Y | N |
В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает "Y", если в его полоске найдется место, где рядом лежат плитки цветов А и Б и "N" в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали — если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски.
Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски.
Петя хочет узнать, сколько различных полосок имеет определенную диаграмму смежности. Помогите ему.
(Заметьте, что полоски, являющиеся отражением друг друга, но не совпадающие, считаются разными. Так, полоска
| С | К | З | К | К | З | С | К | К | К |
Формат входных данных
Первая строка входного файла содержит число N (1 <= N <= 100). Следующие три строки входного файла, содержащие по три символа из набора {"Y", "N"}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична.
Формат выходных данных
Выведите в выходной файл количество полосок длины N, имеющих приведенную во входном файле диаграмму смежности.
Решение
Задачи
Задача 102778[Последовательности из 0 и 1 ] |
|
|
Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100).
Выходные данные
В выходной файл вывести количество искомых последовательностей.
Пример входного файла
5
Пример выходного файла
13
|
|
Решение |
Задача 102779[Восстановление скобок ] |
|
|
Входные данные
Первая строка входного файла содержит заданный шаблон длиной не более 80 символов.
Выходные данные
Выведите в выходной файл искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2·109 .
Пример входного файла
????(?
Пример выходного файла
2
|
|
|
Решение |
Задача 76260 |
|
|
|
|
|
Решение |
Задача 98721[Плитки] |
|
|
| К | К | К | С | З | К | К | З | К | С |
(буквой К обозначена красная плитка, С — синяя, З — зеленая).
После этого Петя заполняет следующую таблицу:
| Красный | Синий | Зеленый | |
| Красный | Y | Y | Y |
| Синий | Y | N | Y |
| Зеленый | Y | Y | N |
В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает "Y", если в его полоске найдется место, где рядом лежат плитки цветов А и Б и "N" в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали — если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски.
Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски.
Петя хочет узнать, сколько различных полосок имеет определенную диаграмму смежности. Помогите ему.
(Заметьте, что полоски, являющиеся отражением друг друга, но не совпадающие, считаются разными. Так, полоска
| С | К | З | К | К | З | С | К | К | К |
Формат входных данных
Первая строка входного файла содержит число N (1 <= N <= 100). Следующие три строки входного файла, содержащие по три символа из набора {"Y", "N"}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична.
Формат выходных данных
Выведите в выходной файл количество полосок длины N, имеющих приведенную во входном файле диаграмму смежности.
|
|
|
Решение |
Задача 64170 |
|
|
Треугольник Паскаля Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая содержит на одно число больше, чем предыдущая. Первое и последнее из этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него. Входные данные. В файле INPUT.TXT записано одно число N (0<=N<=30). Выходные данные. В файл OUTPUT.TXT вывести N строк треугольника Паскаля. Примечание. Все числа в треугольнике Паскаля при указанных ограничениях входят в Longint. Пример файла INPUT.TXT 8 Пример файла OUTPUT.TXT 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1
|
|
|
Решение |
Страница: << 1 2 3 [Всего задач: 15]
