ケーキの問題

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で調べているのでパスすべきですが・・・

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

ではでは。