Какое количество различных прямоугольников можно вырезать из листа бумаги размером N x M, если все клетки пронумерованы различными числами? Программа получает на вход два целых положительных числа N и M, которые не превышают 75000. Необходимо вывести одно число - общее количество прямоугольников, включая весь лист целиком.

Информатика 8 класс Комбинаторика и алгоритмы информатика 8 класс количество прямоугольников лист бумаги размер N x M клетки программа целые положительные числа общее количество алгоритм комбинаторика математика прямоугольники задача вычисления входные данные выходные данные Новый

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

Каждый прямоугольник определяется двумя горизонтальными и двумя вертикальными линиями. На листе размером N x M можно провести N + 1 горизонтальную линию (по краям листа и между строками) и M + 1 вертикальную линию (по краям листа и между столбцами).

Таким образом, для выбора двух горизонтальных линий из N + 1 доступных, мы можем использовать комбинации. Количество способов выбрать 2 линии из N + 1 можно выразить через формулу:

• Количество способов выбрать 2 линии = C(N + 1, 2) = (N + 1) * N / 2

Аналогично, для вертикальных линий:

• Количество способов выбрать 2 линии = C(M + 1, 2) = (M + 1) * M / 2

Теперь, чтобы найти общее количество прямоугольников, нужно перемножить количество способов выбора горизонтальных линий и количество способов выбора вертикальных линий:

• Общее количество прямоугольников = C(N + 1, 2) * C(M + 1, 2)

Подставляя формулы, получаем:

• Общее количество прямоугольников = ((N + 1) * N / 2) * ((M + 1) * M / 2)

Таким образом, итоговая формула для подсчета общего количества прямоугольников, которые можно вырезать из листа размером N x M, выглядит следующим образом:

• Общее количество прямоугольников = (N * (N + 1) * M * (M + 1)) / 4

Теперь, зная эту формулу, можно легко вычислить количество прямоугольников для любых значений N и M, не превышающих 75000.