|
Название задачи: Альтернативные пути . |
 |
Условие
Задано прямоугольную таблицу размером M строк на N столбиков. В каждой клеточке записано натуральное число, не превышающее 200. Путник должен пройти по этой таблице из левого верхнего угла в правый нижний, на каждом шаге перемещаясь либо на 1 клеточку направо, либо на 1 клеточку вниз. Очевидно, таких путей много. Для каждого пути можно вычислить сумму чисел в пройденных клеточках. Среди этих сумм, очевидно, есть максимальная.
Будем снисходительными к Путнику, считая <хорошими> не только пути, на которых в точности достигается максимально возможная сумма, а еще и пути, сумма которых отличается от максимальной не более чем на K.
Количество <хороших> путей гарантированно не превышает 109.
Задание
Напишите программу 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 |
Также доступны документы в формате DOC
Решение
Подробный разбор задачи в формате pdf (740K) на украинском языке,
Решения членов жюри Всеукраинской олимпиады
Тесты
