結果

問題 No.10 ＋か×か
ユーザー らっしー(raccy)
提出日時 2015-10-21 23:46:46
言語 Ruby
(3.4.1)
結果
AC  
実行時間 124 ms / 5,000 ms
コード長 1,354 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 13,952 KB
最終ジャッジ日時 2024-12-14 15:32:41
合計ジャッジ時間 2,076 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

class NiseOCR
  def initialize(list)
    @list = list
    @minmax_list = list.inject([[1, 0]]) do |accs, i|
      accs << [
        [accs[-1][0] + i, accs[-1][0] * i].min,
        [accs[-1][1] + i, accs[-1][1] * i].max,
      ]
    end
    @memory = {}
  end

  def calc(total, point)
    pair = [total, point]
    return @memory[pair] if @memory.include?(pair)
    kaito_list = []

    if point == 0
      if total == @list[point]
        return ''
      else
        @memory[pair] = nil
        return
      end
    end

    # *
    if total % @list[point] == 0
      next_total = total / @list[point]
      if @minmax_list[point][0] <= next_total &&
          next_total <= @minmax_list[point][1]
        if (next_calc = calc(next_total, point - 1))
          kaito_list << next_calc + '*'
        end
      end
    end

    # +
    next_total = total - @list[point]
    if @minmax_list[point][0] <= next_total &&
        next_total <= @minmax_list[point][1]
      if (next_calc = calc(next_total, point - 1))
        kaito_list << next_calc + '+'
      end
    end
    if kaito_list.empty?
      @memory[pair] = nil
      return
    else
      kaito = kaito_list.max
      @memory[pair] = kaito
      return kaito
    end
  end
end

n = gets.to_i
total = gets.to_i
list = gets.split.map(&:to_i)
nocr = NiseOCR.new(list)

puts nocr.calc(total, n - 1)
0