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よりは小さくなります。

さて,結局ケーキの並べ方によって,必要な寸法が変わります。 そのうち,与えられた箱の幅よりも小さくなるような並べ方が見つかれば可, 全て調べて無理なら不可。

となるわけです。

いわゆる「同じものを含む順列」で,逆順は省いて検証するというのが, すぐに思いつく解法ですが,

  1. 「同じものを含む順列」の場合,ある順番の「次」を見つけるアルゴリズムって?

(例) 上の例で,5,4,6,4,8,5,4の次の並べ方は?

  1. 更に逆順を省くアルゴリズムは?

(例) 昇順で調べていく場合,5,4,6,4,8,5,4は既に4,5,8,4,6,4,5で調べているのでパスすべきですが・・・

です。 実際に組んでみると面白いので,試してみてください。

ではでは。


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2008-02-01 (金) 17:14:06 (4987d)