*[[Problem 256:http://projecteuler.net/problem=256]] 「畳禁止の部屋」 [#id63fe03]

畳とは, 部屋の床を重なりなく敷き詰めるのに使われる長方形の敷物である.

手に入る畳の寸法を 1x2 のみと仮定すると, 敷き詰める部屋の形や大きさには明らかにいくらかの制約がある.

本問では, 整数の寸法 a, b, 偶数の大きさ s = a・b をもつ長方形の部屋のみを考える. 「大きさ」という言葉は部屋の表面積を表すのに用い, また一般性を失わないよう a ≦ b という条件を加える.

畳を並べるに当たって1つのルールがある:4 枚の異なる畳の角が合う箇所があってはならない. 例えば, 4x4 の部屋に対し下記の二つの並べ方を考える:

#ref(http://projecteuler.net/project/images/p256_tatami3.gif,center,nolink);

左の並べ方は条件を満たすが, 右は満たさない:中央の赤 "X" は, 4枚の畳が合う箇所を示している.

このルールにより, いくらかの偶数の大きさの部屋は畳を敷くことができない:これらを畳禁止の部屋と呼ぶ.
さらに, 大きさが s となる畳禁止の部屋の数を T(s) と定義する.

最も小さな畳禁止の部屋は, 大きさが s = 70 で寸法が 7x10 である.
大きさが s = 70 の他の部屋はすべて畳を敷くことができる;1x70, 2x35, 5x14 である. ゆえに T(70) = 1 である.

同様に, 大きさが s = 1320 の畳禁止の部屋はちょうど 5 つあるため, T(1320) = 5 であることが確かめられる:20x66, 22x60, 24x55, 30x44, 33x40 である.
実際, s = 1320 は T(s) = 5 となる最も小さな部屋の大きさ s である.

T(s) = 200 となる最も小さな部屋の大きさ s を求めよ.

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS