Версия для печати
Убрать все задачи

---

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

   Решение

Страница: 1 2 >> [Всего задач: 8]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 57838

Темы:   [ Признаки и свойства равнобедренного треугольника. ] [ Удвоение медианы ] [ Центральная симметрия помогает решить задачу ] [ Ромбы. Признаки и свойства ]

Сложность: 2+ Классы: 7,8,9

Докажите, что если в треугольнике медиана и биссектриса совпадают, то треугольник равнобедренный.

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

Решение

---

Задача 57839

Темы:   [ Центральная симметрия помогает решить задачу ] [ Симметричная стратегия ]

Сложность: 3 Классы: 7,8,9

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

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

Решение

---

Задача 57840

Тема:   [ Центральная симметрия помогает решить задачу ]

Сложность: 3 Классы: 9

Окружность пересекает стороны BC, CA, AB треугольника ABC в точках A₁ и A₂, B₁ и B₂, C₁ и C₂ соответственно. Докажите, что если перпендикуляры к сторонам треугольника, проведенные через точки A₁, B₁ и C₁, пересекаются в одной точке, то и перпендикуляры к сторонам, проведенные через A₂, B₂ и C₂, тоже пересекаются в одной точке.

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

Решение

---

Задача 57841

Тема:   [ Центральная симметрия помогает решить задачу ]

Сложность: 3 Классы: 9

Докажите, что прямые, проведенные через середины сторон вписанного четырехугольника перпендикулярно противоположным сторонам, пересекаются в одной точке.

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

Решение

---

Задача 57843

Тема:   [ Центральная симметрия помогает решить задачу ]

Сложность: 3 Классы: 9

Окружности S₁ и S₂ радиуса 1 касаются в точке A; центр O окружности S радиуса 2 принадлежит S₁. Окружность S₁ касается S в точке B. Докажите, что прямая AB проходит через точку пересечения окружностей S₂ и S.

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

Решение

---

Страница: 1 2 >> [Всего задач: 8]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями