← 完整题目索引

PROJECT EULER · #0256

无法铺设榻榻米的房间

Tatami-Free Rooms

仅题目 · 已解决原题 ↗

榻榻米是矩形垫子,用来在不重叠的情况下完全覆盖房间的地面。

假设可用的榻榻米只有 1×2 这一种尺寸,那么能被铺满的房间显然在形状和大小上受到一定限制。

本题只考虑边长 a,b 为整数、面积 s=ab 为偶数的矩形房间。
这里用“大小”表示房间的地面面积;不失一般性,再要求 ab

铺设榻榻米时必须遵守一条规则:不能有四块不同垫子的角在同一点相遇。
例如,考虑下面在 4×4 房间中的两种铺法:

0256_tatami3.gif

左边的铺法符合要求,右边的则不符合:中间红色的“X”标出了四块榻榻米的角相遇的位置。

由于这条规则,有些面积为偶数的房间无法用榻榻米铺满;我们称它们为无法铺设榻榻米的房间。
进一步定义 T(s) 为面积为 s 的这类房间的数量。

最小的这类房间面积为 s=70,尺寸为 7×10
其他面积为 s=70 的房间都可以铺满,它们的尺寸分别为 1×702×355×14
因此,T(70)=1

类似地,可以验证 T(1320)=5,因为面积为 s=1320 的房间中恰好有 5 个无法铺满:
20×6622×6024×5530×4433×40
事实上,s=1320 是满足 T(s)=5 的最小房间面积 s

求满足 T(s)=200 的最小房间面积 s

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。