🐢
[鉄則A28] Blackboard
巨大な値を扱う問題。
問題を要約する
- 整数型の変数に対して演算
+-*を順次行う - その都度、10000 で割った余りを表示する
要点
- 割り算を除く四則演算の途中で 10000 で割った余りに変換しても結果は変わらない
- ただし引き算で負の値になったときは 10000 を足さないと変になる
単純な実装 (TLE)
N = gets.to_i
MOD = 10000
TA = N.times.collect { gets.split } # => [["+", "57"], ["+", "43"], ["*", "100"], ["-", "1"]]
acc = 0
ans = TA.collect do |op, v|
acc = acc.send(op, v.to_i)
end
ans = ans.collect { |e| e.modulo(MOD) } # => [57, 100, 0, 9999]
puts ans
最後に剰余にするのでは手遅れ。
毎回余りに変換する (AC)
169 ms
N = gets.to_i
MOD = 10000
TA = N.times.collect { gets.split } # => [["+", "57"], ["+", "43"], ["*", "100"], ["-", "1"]]
acc = 0
ans = TA.collect do |op, v|
acc = acc.send(op, v.to_i).modulo(MOD) # 毎回余りに変換する
if acc.negative? # 0 未満なら
acc += MOD # 足す
end
acc
end
ans # => [57, 100, 0, 9999]
puts ans
この問題では「途中の値が 0 未満になることはない」と書かれているので「0未満なら足す」処理はなくてもよい。
Discussion