AOJ（問題集）11

AIZU ONLINE JUDGE: Programming Challenge
　

0100 Sale Result

問題が曖昧。同じ社員が二度出てくるかどうかはっきりしない。

Border = 1_000_000

until (n = $<.gets.to_i).zero?
  data = Hash.new(0)
  entry = []
  n.times do
    e, p, q = $<.gets.split.map(&:to_i)
    data[e] += p * q
    entry << e if data[e] >= Border
  end
  puts entry.empty? ? "NA" : entry.uniq
end

0101 Aizu PR

$<.gets.to_i.times do
  text = $<.gets.chomp
  result = ""
  po = 0
  while result.size < text.size
    if text[po, 7] == "Hoshino"
      result += "Hoshina"
      po += 7
    else
      result += text[po]
      po += 1
    end
  end
  puts result
end

0102 Matrix-like Computation

until (n = $<.gets.to_i).zero?
  table = n.times.map do
    l = $<.gets.split.map(&:to_i)
    l + [l.sum]
  end
  last = (n + 1).times.map do |i|
    n.times.map {|j| table[j][i]}.sum
  end
  puts (table + [last]).map {|l| l.map {|i| sprintf("%5d", i)}.join }
end

簡単な問題でも [提出] のボタンを押すときはドキドキするな。
　

0103 Baseball Simulation

$<.gets.to_i.times do
  bases = [0, 0, 0]
  out_count = 0
  points = 0
  while out_count < 3
    case $<.gets.chomp
    when "OUT"
      out_count += 1
      puts points if out_count >= 3
    when "HIT"
      bases << 1
      points += bases.shift
    when "HOMERUN"
      points += bases.sum + 1
      bases = [0, 0, 0]
    else
      raise "error"
    end
  end
end

0104 Magical Tiles

ひさしぶりにやる。

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  tiles = h.times.map {$<.gets.chomp}
  positions = [0]
  x, y = 0, 0
  
  result = loop do
    case tiles[y][x]
    when ">" then x += 1
    when "<" then x -= 1
    when "^" then y -= 1
    when "v" then y += 1
    when "." then break "#{x} #{y}"
    else raise "error"
    end
    po = y * w + x
    break "LOOP" if positions.include?(po)
    positions << po
  end
  puts result
end

簡単だけれどドキドキするな。
　

0105 Book Index

index = Hash.new([])

$<.readlines.map do |l|
  a = l.chomp.split
  [a.first, a.last.to_i]
end.each {|word, page| index[word] += [page]}

index.keys.sort.each {|k| puts k, index[k].sort.join(" ")}

0106 Discounts of Buckwheat

table = [[200, 380, 5, 0.8], [300, 550, 4, 0.85], [500, 850, 3, 0.88]]
A, B, C = table.map(&:first)

calc = ->(shop, num) {
  t = table[shop]
  discount = (num / t[2]) * t[2]
  discount * t[1] * t[3] + (num - discount) * t[1]
}

until (soba = $<.gets.to_i).zero?
  min = Float::INFINITY
  (0..soba / C).each do |c|
    pay = calc.(2, c)
    soba1 = soba - c * C
    
    (0..soba1 / B).each do |b|
      pay1 = pay + calc.(1, b)
      soba2 = soba1 - b * B
      
      next if (soba2 % A).nonzero?
      pay2 = pay1 + calc.(0, soba2 / A)
      min = pay2 if pay2 < min
    end
    
  end
  puts min.to_i
end

再帰で解いた方がよかったかな。ごちゃごちゃしたコードだ。
　

0107 Carry a Cheese

until (a = $<.gets.split.map(&:to_i)) == [0, 0, 0]
  $<.gets.to_i.times.map {$<.gets.to_i}.each do |r|
    result = a.combination(2).map do |w, h|
      Math.sqrt((w / 2.0) ** 2 + (h / 2.0) ** 2) < r
    end.any?
    puts result ? "OK" : "NA"
  end
end

0108 Operation of Frequency of Appearance

def operation(ary, prev = [], i = 0)
  return i - 1, ary if ary == prev
  count = Hash.new(0)
  ary.each {|x| count[x] += 1}
  operation(ary.map {|x| count[x]}, ary, i + 1)
end

until $<.gets.to_i.zero?
  i, ary = operation($<.gets.split.map(&:to_i))
  puts i, ary.join(" ")
end

0109 Smart Calculator

$<.gets.to_i.times do
  splited = $<.gets.chomp.scan(/([0-9\.]+|\+|\-|\*|\/|\(|\)|=)/)
  output = []
  stack = []
  a = nil
  until (token = splited.shift) == ["="]
    token = token.first
    case token
    when "(" then stack << token
    when ")" then
      output << a until (a = stack.pop) == "("
    when "*", "/"
      loop do
        a = stack.last
        break unless %w(* /).include?(a)
        output << stack.pop
      end
      stack << token
    when "+", "-"
      loop do
        a = stack.last
        break unless %w(+ - * /).include?(a)
        output << stack.pop
      end
      stack << token
    else
      output << token
    end
  end
  output << a while (a = stack.pop)
  
  stack = []
  while (x = output.shift)
    if %w(+ - * /).include?(x)
      a, b = stack.pop, stack.pop
      stack << eval("#{b} #{x} #{a}").to_i
    else
      stack << x
    end
  end
  puts stack.first
end

何がいけないのかわからない。
どうしてもわからないので他人の回答を見た。喰らった…。

$<.gets.to_i.times do
  splited = $<.gets.chomp.scan(/([0-9\.]+|\+|\-|\*|\/|\(|\)|=)/)
  a = nil
  
  # パーサー（逆ポーランド記法に変換）
  output = []
  stack = []
  until (token = splited.shift) == ["="]
    token = token.first
    case token
    when "(" then stack << token
    when ")" then
      output << a until (a = stack.pop) == "("
    when "*", "/"
      loop do
        a = stack.last
        break unless %w(* /).include?(a)
        output << stack.pop
      end
      stack << token
    when "+", "-"
      loop do
        a = stack.last
        break unless %w(+ - * /).include?(a)
        output << stack.pop
      end
      stack << token
    else
      output << token.to_r
    end
  end
  output << a while (a = stack.pop)
  
  # 逆ポーランド記法を処理
  stack = []
  while (x = output.shift)
    if %w(+ - * /).include?(x)
      a, b = stack.pop, stack.pop
      if x == "/" and ((a < 0) ^ (b < 0))
        stack << -(b.abs / a.abs)
      else
        stack << eval("#{b.to_i} #{x} #{a.to_i}").to_i
      end
    else
      stack << x
    end
  end
  puts stack.first.to_i
end

これを見てほしい。

$ pry
[1] pry(main)> -3/2
=> -2

マジか！ -1 ではないのか！

div はメソッド / を呼びだし、floorを取ることで計算されます。

class Numeric (Ruby 2.5.0)

やられた。そういう Ruby の仕様なのね。勉強になりました。せっかくパーサー（操車場アルゴリズム）まで書いて頑張ったのに…。なお、皆さん演算子の再定義でやっておられる。自分もそれは考えたが、それではつまらん。