Задача 147
Прямоугольники в заштрихованных решетках

В диагонально заштрихованную решетку 3x2 всего можно вместить 37 различных прямоугольников, как это показано на схеме ниже.

Существует 5 решеток меньше 3x2, при этом учитывается различие между вертикальным и горизонтальным измерением, т.е.: 1x1, 2x1, 3x1, 1x2 и 2x2. Если все эти решетки являются диагонально заштрихованными, то в каждую из них можно вместить следующее количество прямоугольников:

1x1: 1
2x1: 4
3x1: 8
1x2: 4
2x2: 18

Добавив все эти значения к имеющимся 37, полученным решеткой 3х2, в итоге получим 72 прямоугольника, которые можно вместить в решетки, размеры которых не превышают 3x2.

Сколько различных прямоугольников можно вместить в решетки, размеры которых не превышают 47x43?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net