結果

問題 No.10 ＋か×か
ユーザー vjudge1
提出日時 2025-09-05 10:36:31
言語 Crystal
(1.14.0)
結果
RE  
実行時間 -
コード長 767 bytes
コンパイル時間 16,632 ms
コンパイル使用メモリ 311,708 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-05 10:36:49
合計ジャッジ時間 13,204 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, t = read_line.split.map(&.to_i64)
a = Array(Int64).new(n) { read_line.to_i64 }

# Initialize DP table
dp = Array(Array(Bool)).new(n + 1) { Array(Bool).new(t + 1, false) }
dp[n][t] = true

# Fill DP table backwards
(n - 1).downto(0) do |i|
  (1..t).each do |j|
    if dp[i + 1][j]
      if j - a[i] >= 0
        dp[i][j - a[i]] = true
      end
      if j % a[i] == 0
        dp[i][j // a[i]] = true
      end
    end
  end
end

unless dp[0][0]
  puts -1
else
  ans = ""
  s = a[0]
  (1...n).each do |i|
    if s + a[i] <= t && dp[i + 1][s + a[i]]
      ans += '+'
      s += a[i]
    elsif s * a[i] <= t && dp[i + 1][s * a[i]]
      ans += '*'
      s *= a[i]
    else
      raise "Invalid state"
    end
  end
  raise "Invalid result" unless s == t
  puts ans
end
0