Задача 256
Комнаты без татами

Татами - прямоугольные маты, которыми полностью покрывают пол комнаты, без перекрытий.

Предположим, что единственный возможный вид татами имеет размеры 1×2, очевидно, что на размер и форму комнаты накладываются некоторые ограничения, чтобы пол комнаты можно было покрыть целиком.

В данной задаче мы рассматриваем только комнаты прямоугольной формы с целыми размерами a, b и четным размером s = a·b.
Под термином 'размер' мы подразумеваем площадь поверхности пола комнаты и, без потери условия обобщенности, добавим требование ab.

При покрытии татами есть одно правило, которому необходимо следовать: не должно быть ни одной такой точки, где происходил бы стык четырех разных матов.
К примеру, рассмотрим два варианта покрытия пола комнаты 4×4 ниже:


Вариант покрытия слева приемлем, в то время как правый вариант - нет: красный символ "X" в середине указывает место стыка четырех матов татами

Из-за такого правила, даже для комнат с четными размерами не всегда можно покрыть пол татами: такие комнаты мы будем называть комнатами без татами.
Далее, определим T(s) как число комнат без татами размером s.

Наименьшая комната без татами имеет размер s = 70 и размерности 7×10.
Полы всех остальных комнат размером s = 70 можно покрыть татами; размерности таких комнат: 1×70, 2×35 и 5×14.
Значит, T(70) = 1.

Аналогично, мы можем убедиться в том, что T(1320) = 5, т.к. существует ровно 5 комнат без татами размером s = 1320:
20×66, 22×60, 24×55, 30×44 и 33×40.
К слову, s = 1320 является наименьшим размером s комнаты, для которой T (s) = 5.

Найдите наименьший размер комнаты s, при котором T(s) = 200.

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