На некоторые клетки квадратной доски 4×4 выкладывают стопкой золотые монеты, а на остальные клетки – серебряные. Можно ли положить монеты так, чтобы в каждом квадрате 3×3 серебряных монет было больше, чем золотых, а на всей доске золотых было больше, чем серебряных?

   Решение

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

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

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

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

   Решение

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

Рассматривается произвольный многоугольник (не обязательно выпуклый).
  а) Всегда ли найдётся хорда многоугольника, которая делит его на две равновеликие части?
  б) Докажите, что любой многоугольник можно разделить некоторой хордой на части, площадь каждой из которых не меньше чем ⅓ площади многоугольника. (Хордой многоугольника называется отрезок, концы которого принадлежат контуру многоугольника, а сам он целиком принадлежит многоугольнику, включая контур.)

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

Решение

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