鱼C论坛

 找回密码
 立即注册
查看: 2680|回复: 0

题目256:榻榻米免疫房间

[复制链接]
发表于 2017-1-13 15:03:57 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
Tatami-Free Rooms

Tatami are rectangular mats, used to completely cover the floor of a room, without overlap.

Assuming that the only type of available tatami has dimensions 1×2, there are obviously some limitations for the shape and size of the rooms that can be covered.

For this problem, we consider only rectangular rooms with integer dimensions a, b and even size s = a·b.
We use the term 'size' to denote the floor surface area of the room, and — without loss of generality — we add the condition a ≤ b.

There is one rule to follow when laying out tatami: there must be no points where corners of four different mats meet.
For example, consider the two arrangements below for a 4×4 room:

p256_tatami3.gif


The arrangement on the left is acceptable, whereas the one on the right is not: a red "X" in the middle, marks the point where four tatami meet.

Because of this rule, certain even-sized rooms cannot be covered with tatami: we call them tatami-free rooms.
Further, we define T(s) as the number of tatami-free rooms of size s.

The smallest tatami-free room has size s = 70 and dimensions 7×10.
All the other rooms of size s = 70 can be covered with tatami; they are: 1×70, 2×35 and 5×14.
Hence, T(70) = 1.

Similarly, we can verify that T(1320) = 5 because there are exactly 5 tatami-free rooms of size s = 1320:
20×66, 22×60, 24×55, 30×44 and 33×40.
In fact, s = 1320 is the smallest room-size s for which T(s) = 5.

Find the smallest room-size s for which T(s) = 200.


题目:

榻榻米是矩形垫,用于完全覆盖一个房间的地板却不产生重叠。

假设仅有一种榻榻米,它的规格是 1×2,显然对于能够覆盖的房间的形状与尺寸有一些限制。

对于这个问题,我们仅考虑规格为整数 a,b 且面积 s 为偶数(s=a·b )的矩形房间。
我们用术语 '尺寸' 来表示房间地板的表面积,不失一般性,我们令 a ≤ b。

当放置榻榻米时仅须遵守一条规则:不允许有 4 个不同的垫子在一点相交。

例如,考虑下面对于 4x4 房间的两种安排

p256_tatami3.gif


左边的安排是允许的,然而右边的是不允许的:中间的红色 "X" 标记了 4 个榻榻米在此相交。

由于这条规则,特定的偶数尺寸的文章不能被榻榻米覆盖:我们称之为榻榻米免疫房间。

进一步,我们定义 T(s) 为尺寸为 s 的榻榻米免疫房间的个数。

最小的榻榻米免疫房间的尺寸 s=70 并有规格 7x10。

所有其它尺寸为 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 是使得 T(s) = 5 的最小的房间尺寸。

求使得 T(s) = 200 的最小的房间尺寸。


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-22 18:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表