結果

問題 No.10 ＋か×か
コンテスト
ユーザー vjudge1
提出日時 2025-09-05 10:48:20
言語 Crystal
(1.14.0)
結果
WA  
実行時間 -
コード長 996 bytes
コンパイル時間 17,596 ms
コンパイル使用メモリ 311,700 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-05 10:48:39
合計ジャッジ時間 12,851 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = gets.not_nil!.to_i
t = gets.not_nil!.to_i
a = gets.not_nil!.split.map(&.to_i)

# Use hash-based DP to avoid bounds issues completely
dp = Array(Hash(Int32, Bool)).new(n + 1) { Hash(Int32, Bool).new }
dp[n][t] = true

# Fill DP table backwards
(n - 1).downto(0) do |i|
  dp[i + 1].each_key do |current_val|
    # Check subtraction
    if current_val >= a[i]
      prev_val = current_val - a[i]
      dp[i][prev_val] = true
    end
    
    # Check division (only if divisible)
    if a[i] != 0 && current_val % a[i] == 0
      prev_val = current_val // a[i]
      dp[i][prev_val] = true
    end
  end
end

# Check if solution exists
unless dp[0].has_key?(a[0])
  puts -1
else
  # Reconstruct the solution
  ans = ""
  current = a[0]
  (1...n).each do |i|
    if dp[i + 1].has_key?(current + a[i])
      ans += '+'
      current += a[i]
    elsif dp[i + 1].has_key?(current * a[i])
      ans += '*'
      current *= a[i]
    else
      raise "Invalid solution path"
    end
  end
  puts ans
end
0