Формат входных данных
На вход подаются четыре натуральных числа n
, m
, x
, y
, каждое в отдельной строке. 1≤n
, m≤31622
, 1≤x≤n
, 1≤y≤m
.
Формат выходных данных
Выведите одно неотрицательное целое число —
количество способов выделить на поле один прямоугольный участок земли со сторонами, расположенными на сетке, и не содержащий внутри квадрат с камнем. Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64
‑битный тип данных, например, long long в C++, int64
в Free Pascal, long в Java.Ввод
Вывод
3
3
2
3
24
4
5
2
4
102
Код
Python 3
python
n = int(input())
m = int(input())
x = int(input())
y = int(input())
count = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
a = max(1, i - y)
b = min(n, i + x)
c = max(1, j - x)
d = min(m, j + y)
count += (b - a + 1) * (d - c + 1)
print(count)
Данный код имеет сложность O(n * m), что является приемлемым для указанных диапазонов значений n и m. Однако, если входные данные будут иметь большие значения n и m, то данное решение может работать долго. В таком случае можно рассмотреть оптимизацию алгоритма, например, использование динамического программирования или поиск другой математической формулы для подсчета количества способов.Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет