Каталог по источникам

Задачи

Страница: << 38 39 40 41 42 43 44 >> [Всего задач: 272]

Задача 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.

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

Задача 98848

[Счет игры ]

Тема:

[

Площадь

]

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

Задана квадратная доска размером N×N. Известно, что на ней играли в интеллектуальную игру, вследствие чего клеточки оказались окрашенными в белый, чёрный и зеленый цвета. Раскраска клеточек может быть разной (ведь это интеллектуальная игра!), но все клеточки самого верхнего ряда белые, а самого нижнего - чёрные.

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

Определение чёрной области выглядит аналогично: она ограничена снизу нижней стороной квадрата, с других сторон - чёрной границей, которая проходит только через чёрные клеточки, а концы этой границы - левая нижняя и правая нижняя клеточки квадрата.

Задание

Напишите программу SCORE, которая по раскраске квадрата находит количество клеточек в белой и чёрной областях.

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

Первая строка входного файла SCORE.DAT содержит единственное целое число N - размер квадрата (5≤N?250). Каждая из следующих N строк содержит по N символов "G", "W" или "B" (записанных без пробелов), которые обозначают зелёный, белый и чёрный цвет, соответственно.

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

Первая строка выходного файла SCORE.SOL должна содержать количество клеточек в белой области, а вторая строка - количество клеточек в чёрной области.

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

SCORE.DAT	SCORE.SOL
7 WWWWWWW WGWWBWG WWWWGWW BBGWWWB GWBBWGB BBBBGBB BBBBBBB	22 15

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

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

Решение

Задача 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

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

Решение

Страница: << 38 39 40 41 42 43 44 >> [Всего задач: 272]