公平に分けられたケーキ

q56a.rb

#(x, y)のケーキを切ってできる全ての (面積, 切った長さの合計) のペアを返す
#ただし面積はここでカットした人の総計
def cut(x, y)
  x, y = y, x if x < y
  return @memo[[x, y]] if @memo.has_key?([x, y])
  return {1 => 1} if x == 2 and y == 1
  
  result = {}
  
  #前の人がカットしたところから自分の分を求める
  #「if result[square] > length」は効果の大きい枝刈り（切り口の長さの総和が最小になるものだけ残す）
  calc = proc do |s, t|
    cut(s, t).each do |sqar, ln|
      square = x * y - sqar
      length = ln + s
      result[square] = length if !result.has_key?(square) or result[square] > length
    end
  end
  
  #可能なあらゆる場合でケーキを切る
  (x / 2).times {|i| calc.(y, x - i - 1)}
  (y / 2).times {|i| calc.(x, y - i - 1)}
  
  @memo[[x, y]] = result
end

X, Y = 16, 12
@memo = {}

result = cut(X, Y)
p result.select {|sqar, _| sqar == X * Y / 2}    #=>{96=>47}