Ограничение по времени: 1
секунда
Ограничение по памяти: 256
мегабайт
Администрация города решила разбить парк на пустыре площадью N×M
. В парке планируется высадить деревья. Для каждого дерева нужно выделить участок прямоугольной формы с целочисленными сторонами и площадью, равной S
.
Все участки должны быть равны, одинаково ориентированы, и их стороны должны быть параллельны сторонам пустыря.
Какое наибольшее количество деревьев можно высадить в парке?
python
def max_trees(N, M, S):
max_count = 0
if N * M < S:
return max_count
for a in range(1, N+1):
for b in range(1, M+1):
if a * b <= S:
count = (N // a) * (M // b)
max_count = max(max_count, count)
return max_count
В данной реализации функция `max_trees` принимает три аргумента: `N` — длина пустыря, `M` — ширина пустыря и `S` — площадь участка. Она возвращает максимальное количество деревьев, которое можно разместить на данном парке.
Сначала функция проверяет условие, при котором размещение деревьев невозможно — если площадь пустыря меньше площади участка. В этом случае она возвращает 0, так как ни одно дерево нельзя разместить на таком парке.
Затем при помощи двух вложенных циклов `for` перебираются все возможные размеры участков. Внешний цикл перебирает значения стороны `a` от 1 до `N`, а внутренний цикл перебирает значения стороны `b` от 1 до `M`. Для каждой комбинации `a` и `b` вычисляется количество участков, которое вмещается на пустыре с помощью операции целочисленного деления: `(N // a)` и `(M // b)`. Затем эти значения перемножаются и сохраняются в переменную `count`.
Далее сравнивается текущее значение `count` с максимальным количеством деревьев (`max_count`), найденным ранее. Если текущее значение больше, оно становится новым максимальным количеством.
После окончания всех итераций по двум вложенным циклам функция возвращает максимальное количество деревьев, найденное во время перебора.
Данное решение имеет временную сложность O(N*M), так как перебор осуществляется по всем возможным размерам участков на пустыре площадью N×M. В худшем случае, когда N и M достигают своих максимальных значений, временная сложность может достичь O(N^2 * M^2).Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет