NetaTaneMenu? >>>> ケーキの問題 ケーキの問題何年か前のプログラミングのコンテストに出た問題からです。 あるケーキ屋さんがロールケーキを出荷します。 ただし,ロールケーキ(切り口は真円)のサイズはまちまちで, 半径が3から10までの整数値でできあがってきます。 これらを7個から12個ずつまとめて箱に並べて出荷します。 問題は,箱の幅とケーキの数とそれぞれの寸法が与えられた時に, ケーキが上手く箱に収まるかどうか判定するプログラムを書きなさい, というものです。 (以下,考える手間を省くための説明) 例えば,4,4,4,5,5,6,8という寸法のケーキが与えられた時, 必要な箱の幅は(4+4+4+5+5+6+8)×2というわけではありません。 半径8のケーキの横に半径4のケーキを並べると, 2つのケーキの幅は,明らかに(8+4)×2よりは小さくなります。 さて,結局ケーキの並べ方によって,必要な寸法が変わります。 そのうち,与えられた箱の幅よりも小さくなるような並べ方が見つかれば可, 全て調べて無理なら不可。 となるわけです。 いわゆる「同じものを含む順列」で,逆順は省いて検証するというのが, すぐに思いつく解法ですが,
(例) 上の例で,5,4,6,4,8,5,4の次の並べ方は?
(例) 昇順で調べていく場合,5,4,6,4,8,5,4は既に4,5,8,4,6,4,5で調べているのでパスすべきですが・・・ です。 実際に組んでみると面白いので,試してみてください。 ではでは。 |