id:torazuka:20130626:balls
の問題からヒントを得て。
「あなたはn個の同じサイズのボールを持っています。(n-1)個は同じ重さで、1つだけが他より少し重いです。秤をm回かそれ以下の回数使って、少しだけ重いボールを見つけるには、どうすればよいでしょうか？」という問題を B(n,m) と呼ぼう。
n, m は正の整数。
- B(n, m) が解を持つのはどんな時か。
- B(n, m) が解を持つ場合に、その手順を実装せよ。ただし、n<10000。ボールの重さ w は整数で 1≦w≦10000 としてよい。
1問目はある程度有名な問題だと思う。
2問目は有名かどうか知らない。
ちなみにどう書く( http://atnd.org/events/40389 )用の問題じゃないので、事前に解いたりはしてないよ。
それほど苦しまずに解けそうだとは思っているけれど。
