ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при поддержке
ЦПМ
Подтемы:
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 2593 2594 2595 2596 2597 2598 2599 >> [Всего задач: 21755]      



Задача 98853

 [Альтернативные пути ]
Тема:   [ Динамическое программирование (прочее) ]
Сложность: 3+

Задано прямоугольную таблицу размером 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

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

Задача 102212

Темы:   [ Теорема синусов ]
[ Произведение длин отрезков хорд и длин отрезков секущих ]
Сложность: 3+
Классы: 8,9

Через вершины B и C треугольника ABC проведена окружность, которая пересекает сторону AB в точке K и сторону AC в точке L. Найдите AB, если AK = KB, AL = l, $ \angle$BCK = $ \alpha$, $ \angle$CBL = $ \beta$.
Прислать комментарий     Решение


Задача 102239

Темы:   [ Отношение, в котором биссектриса делит сторону ]
[ Свойства биссектрис, конкуррентность ]
Сложность: 3+
Классы: 8,9

В треугольнике ABC на сторонах AB и BC отмечены точки M и N соответственно, причём BM = BN. Через точку M проведена прямая, перпендикулярная BC, а через точку N — прямая перпендикулярная AB. Эти прямые пересекаются в точке O. Продолжение отрезка BO пересекает сторону AC в точке P и делит её на отрезки AP = 5 и PC = 4. Найдите длину отрезка BP, если известно, что BC = 6.
Прислать комментарий     Решение


Задача 102286

Темы:   [ Касающиеся окружности ]
[ Теорема Пифагора (прямая и обратная) ]
Сложность: 3+
Классы: 8,9

Две окружности радиусов $ \sqrt{19}$ и $ \sqrt{76}$, касающиеся друг друга внешним образом, вписаны в полуокружность (т.е. каждая из окружностей касается этой полуокружности и её диаметра). Найдите радиус полуокружности.
Прислать комментарий     Решение


Задача 102287

Темы:   [ Касающиеся окружности ]
[ Теорема Пифагора (прямая и обратная) ]
Сложность: 3+
Классы: 8,9

Две окружности, касающиеся друг друга внешним образом, вписаны в полуокружность радиуса 4$ \sqrt{13}$ (т.е. каждая из окружностей касается этой полуокружности и её диаметра). Найдите радиус большей окружности, если радиус меньшей окружности равен $ \sqrt{13}$.
Прислать комментарий     Решение


Страница: << 2593 2594 2595 2596 2597 2598 2599 >> [Всего задач: 21755]      



© 2004-... МЦНМО (о копирайте)
Пишите нам