Каталог по темам

Задачи

Страница: << 14 15 16 17 18 19 20 >> [Всего задач: 155]

Задача 98831

Тема:

[

Нерекурсивная генерация объектов

]

Сложность: 3+

Представляя по-прежнему разбиения как невозрастающие последовательности, перечислить их в порядке, обратном лексикографическому (для n=4, например, должно быть 4, 3+1, 2+2, 2+1+1, 1+1+1+1).

Прислать комментарий Решение

Задача 98832

Тема:

[

Нерекурсивная генерация объектов

]

Сложность: 3+

Представляя разбиения как неубывающие последовательности, перечислить их в лексикографическом порядке. Пример для n=4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4.

Прислать комментарий Решение

Задача 98833

Тема:

[

Нерекурсивная генерация объектов

]

Сложность: 3+

Представляя разбиения как неубывающие последовательности, перечислить их в порядке, обратном лексикографическому. Пример для n=4: 4, 2+2, 1+3, 1+1+2, 1+1+1+1.

Прислать комментарий Решение

Задача 98853

[Альтернативные пути ]

Тема:

[

Динамическое программирование (прочее)

]

Сложность: 3+

Задано прямоугольную таблицу размером M строк на N столбиков. В каждой клеточке записано натуральное число, не превышающее 200. Путник должен пройти по этой таблице из левого верхнего угла в правый нижний, на каждом шаге перемещаясь либо на 1 клеточку направо, либо на 1 клеточку вниз. Очевидно, таких путей много. Для каждого пути можно вычислить сумму чисел в пройденных клеточках. Среди этих сумм, очевидно, есть максимальная.

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

Количество <хороших> путей гарантированно не превышает 10⁹.

Задание

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

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

Первая строка входного файла GOODWAYS.DAT содержит три целых числа M (2≤M≤200), N (2≤N≤200) и K (0≤K≤200). Каждая из последующих M строк содержит N чисел, записанных в соответствующих клеточках.

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

Первая строка выходного файла GOODWAYS.SOL должна содержать максимальную возможную сумму; вторая строка - количество маршрутов, сумма чисел которых отличается от максимальной не более чем на K.

Пример входных и выходных данных

GOODWAYS.DAT	GOODWAYS.SOL
2 3 3 1 9 7 2 5 3	20 2

Прислать комментарий

Решение

Задача 102782

[Дырокол ]

Темы:	[	Динамическое программирование (прочее)	]
Темы:	[	Длинная арифметика как инструмент	]

Сложность: 3+

Квадратный клетчатый лист бумаги 2^N × 2^N клеток начинают складывать следующим образом. Сначала нижняя половина листа накладывается на верхнюю, затем правая половина листа накладывается на левую. Эту операцию повторяют N-3 раза, в результате чего получается сложенный лист 8 × 8 клеток. Какие-то из клеток этого сложенного листа удаляются при помощи дырокола.

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

Входные данные
Первая строка входного файла содержит целое число N (4 ≤ N ≤ 500). В следующих 8 строках записана матрица 8 × 8 из нулей и единиц, разделенных пробелом. Единицами отмечены клетки, выкалываемые дыроколом из сложенного листа 8 × 8.

Выходные данные
Вывести в выходной файл искомое число частей.

Пример входного файла
4
0 1 0 0 0 0 1 0
1 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0

Пример выходного файла
11

Прислать комментарий Решение

Страница: << 14 15 16 17 18 19 20 >> [Всего задач: 155]