結果

問題 No.10 ＋か×か
ユーザー neko_the_shadowneko_the_shadow
提出日時 2019-05-29 16:33:19
言語 Ruby
(3.3.0)
結果
WA  
実行時間 -
コード長 569 bytes
コンパイル時間 41 ms
コンパイル使用メモリ 11,912 KB
実行使用メモリ 55,980 KB
最終ジャッジ日時 2023-10-17 18:42:22
合計ジャッジ時間 5,629 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 90 ms
16,092 KB
testcase_01 AC 83 ms
16,088 KB
testcase_02 AC 83 ms
16,092 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 84 ms
16,092 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 256 ms
30,608 KB
testcase_10 AC 85 ms
16,352 KB
testcase_11 AC 85 ms
16,088 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

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

# +: 0
# *: 1
# pass: inf
dp = Array.new(n + 1){ Array.new(t + 1, Float::INFINITY) }
dp[1][a[0]] = -1
(1...n).each do |x|
  (0..t).each do |y|
    next if dp[x][y] == Float::INFINITY
    dp[x + 1][y + a[x]] = [dp[x + 1][y + a[x]], 0].min if y + a[x] <= t
    dp[x + 1][y * a[x]] = [dp[x + 1][y * a[x]], 1].min if y * a[x] <= t
  end
end

stack = []
n.downto(2).each do |x|
  op = dp[x][t]
  if op == 0
    stack << "+"
    t -= a[x - 1]
  else
    stack << "*"
    t /= a[x - 1]
  end
end

puts stack.reverse.join
0