結果

問題 No.10 ＋か×か
コンテスト
ユーザー vjudge1
提出日時 2025-09-05 10:50:53
言語 Crystal
(1.14.0)
結果
WA  
実行時間 -
コード長 1,660 bytes
コンパイル時間 13,769 ms
コンパイル使用メモリ 311,428 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-09-05 10:51:08
合計ジャッジ時間 13,011 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 3 RE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = gets.not_nil!.to_i
total = gets.not_nil!.to_i
list = gets.not_nil!.split.map(&.to_i)

# Precompute minmax_list
minmax_list = Array({Int32, Int32}).new(list.size + 1)
minmax_list << {1, 0}  # Initial state

list.each do |i|
  prev_min, prev_max = minmax_list[-1]
  new_min = [prev_min + i, prev_min * i].min
  new_max = [prev_max + i, prev_max * i].max
  minmax_list << {new_min, new_max}
end

# Memory for memoization
memory = Hash({Int32, Int32}, String?).new

calc = uninitialized (Int32, Int32) -> String?
calc = ->(total_val : Int32, point : Int32) do
  pair = {total_val, point}
  if memory.has_key?(pair)
    return memory[pair]
  end

  if point == 0
    if total_val == list[point]
      memory[pair] = ""
    else
      memory[pair] = nil
    end
    return memory[pair]
  end

  kaito_list = [] of String

  # Multiplication
  if list[point] != 0 && total_val % list[point] == 0
    next_total = total_val // list[point]
    min_val, max_val = minmax_list[point]
    if next_total >= min_val && next_total <= max_val
      if (next_calc = calc.call(next_total, point - 1))
        kaito_list << next_calc + "*"
      end
    end
  end

  # Addition
  next_total = total_val - list[point]
  min_val, max_val = minmax_list[point]
  if next_total >= min_val && next_total <= max_val
    if (next_calc = calc.call(next_total, point - 1))
      kaito_list << next_calc + "+"
    end
  end

  if kaito_list.empty?
    memory[pair] = nil
  else
    # Find the solution with maximum length (or any other criteria)
    kaito = kaito_list.max_by(&.size)
    memory[pair] = kaito
  end

  memory[pair]
end

result = calc.call(total, n - 1)
puts result || -1
0