Задача 563
Роботы-сварщики

Компания специализируется в производстве больших прямоугольных металлических листов, начиная с заготовок размером с единичный квадрат. Сварка выполянется рядом роботов, увеличивающихся в размере. К сожалению, возможности программирования этих роботов очень ограничены. Каждый может обработать лишь не больее 25 одинаковых металлических прямоугольников, которые они могут сварить вдоль одной из сторон, таким образом соединяя их в больший прямоугольник. Единственные рабочие параметры, которые можно запрограммировать - это количество прямоугольников для обработки (до 25 включительно) и по какой стороне их сваривать - длинной или короткой.

Например, первый робот может быть запрограммирован сваривать вместе 11 исходных листов в форме единичного квадрата, производя полосу размером 11×1. Следующий может взять 10 таких полос 11×1 и сварить их или в форме более длинной полосы 110×1, или в форме прямоугольника 11×10. Таким образом можно сформировать металлические листы многих, но не всех возможных размеров.

Один постоянный заказчик делает особенно странные заказы. Он всегда требует, чтобы конечный продукт имел точно указанную площадь, и чтобы его длинная сторона не более, чем на 10% длиннее короткой стороны. Если эти условия возможно выполнить более, чем одним способом (с точки зрения длин сторон), тогда он требует сделать все возможные варианты. Например, если он попросит сделать металлический лист площадью 889200, тогда конечные продукты трех разных размеров смогут удовлетворить это требование: 900×988, 912×975 и 936×950. Заданная площадь 889200 является наименьшей площадью, которую можно произвести тремя различными способами, учитывая ограничения роботов-сварщиков.

Пусть M(n) будет наименьшей площадью, которую можно произвести ровно n вариантами, в которых длинная сторона не более, чем на 10% длиннее короткой стороны. Посему, M(3) = 889200.

Найдите $ \sum_{n=2}^{100} M(n)$.

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