AOJ（問題集）17

AIZU ONLINE JUDGE: Programming Challenge
　

0160 Delivery Fee

table = [[60, 2, 600], [80, 5, 800], [100, 10, 1000],
         [120, 15, 1200], [140, 20, 1400], [160, 25, 1600]]

until (n = $<.gets.to_i).zero?
  result = n.times.map {$<.gets.split.map(&:to_i)}.map do |x, y, h, w|
    idx = table.index {|d| x + y + h <= d[0] and w <= d[1]}
    idx ? table[idx].last : 0
  end.sum
  puts result
end

0161 Sport Meet

until (n = $<.gets.to_i).zero?
  result = n.times.map {$<.gets.split.map(&:to_i)}.map do |id, *d|
    [id, d.each_slice(2).map {|m, s| 60 * m + s}.sum]
  end.sort {|a, b| a[1] <=> b[1]}.map(&:first)
  puts result[0], result[1], result[-2]
end

0162 Hamming Numbers

L = 1000000

table = []
(0..19).each do |a|
  table << (x1 = 2 ** a)
  (1..12).each do |b|
    table << (x2 = 3 ** b)
    y1 = x1 * x2
    table << y1 if y1 <= L
    (1..8).each do |c|
      table << (x3 = 5 ** c)
      y2 = x2 * x3
      y3 = x1 * x3
      y4 = y1 * x3
      table << y2 if y2 <= L
      table << y3 if y3 <= L
      table << y4 if y4 <= L
    end
  end
end
table.uniq!.sort!

until (n = $<.gets.chomp) == "0"
  m, n = n.split.map(&:to_i)
  a = table.bsearch_index {|x| x >= m}
  b = table.bsearch_index {|x| x > n}
  b = b ? b : table.size
  puts b - a
end

0163 Highway Toll

toll = [[0, 300, 500, 600, 700, 1350, 1650],
        [0, 0, 350, 450, 600, 1150, 1500],
        [0, 0, 0, 250, 400, 1000, 1350],
        [0, 0, 0, 0, 250, 850, 1300],
        [0, 0, 0, 0, 0, 600, 1150],
        [0, 0, 0, 0, 0, 0, 500]]
S, E = 17 * 60 + 30, 19 * 60 + 30

until (d = $<.gets.to_i).zero?
  h, m = $<.gets.split.map(&:to_i)
  td = h * 60 + m
  a = $<.gets.to_i
  h, m = $<.gets.split.map(&:to_i)
  ta = h * 60 + m
  
  d, a = a, d if d > a
  f = if (a == 6 and d == 1) or (a == 7 and d <= 3)
    false
  elsif td.between?(S, E) or ta.between?(S, E)
    true
  else
    false
  end
  
  result = toll[d - 1][a - 1]
  result /= 2 if f
  puts ((result / 50.0).ceil * 50).to_i
end

td, ta が S と E の間にあればよいということがなかなかわからなかった。
　

0164 Ohajiki Game

until (n = $<.gets.to_i).zero?
  ary = $<.gets.split.map(&:to_i)
  ohajiki = 32
  loop do
    ohajiki -= (ohajiki - 1) % 5
    puts ohajiki
    a = ary.first
    if ohajiki <= a
      ohajiki = 0
    else
      ohajiki -= a
    end
    puts ohajiki
    break if ohajiki.zero?
    ary.rotate!
  end
end

0165 Lottery

MP = 999983

sieve = [*0..MP]
2.upto(Math.sqrt(MP).to_i) do |i|
  next if sieve[i].zero?
  2.upto(MP / i) {|j| sieve[i * j] = 0}
end
sieve = sieve[2..-1].reject {|x| x.zero?}

until (n = $<.gets.to_i).zero?
  account = n.times.map do
    p, m = $<.gets.split.map(&:to_i)
    s = sieve.bsearch_index {|i| i >= p - m}
    e = sieve.bsearch_index {|i| i > p + m} || sieve.size
    prize = e - s
    prize.zero? ? -1 : prize - 1
  end.sum
  puts account
end

0166 Area of Polygon

until (m = $<.gets.to_i).zero?
  poly1 = (m - 1).times.map {$<.gets.to_i}
  poly1 << 360 - poly1.sum
  n = $<.gets.to_i
  poly2 = (n - 1).times.map {$<.gets.to_i}
  poly2 << 360 - poly2.sum
  
  area1 = poly1.map {|i| Math.sin(i / 180.0 * Math::PI)}.sum
  area2 = poly2.map {|i| Math.sin(i / 180.0 * Math::PI)}.sum
  
  result = case
           when area1 == area2 then 0
           when area1 > area2  then 1
           else 2
           end
  puts result
end

0167 Bubble Sort

def bubble_sort(ary)
  n = ary.size
  co = 0
  (n - 1).downto(1) do |i|
    i.times do |j|
      if ary[j] > ary[j + 1]
        ary[j], ary[j + 1] = ary[j + 1], ary[j]
        co += 1
      end
    end
  end
  co
end

until (n = $<.gets.to_i).zero?
  puts bubble_sort(n.times.map {$<.gets.to_i})
end

0168 Kannondou

@memo = {}

def count(n)
  return @memo[n] if @memo[n]
  result = case n
           when 1 then 1
           when 2 then 2
           when 3 then 4
           else
             count(n - 1) + count(n - 2) + count(n - 3)
           end
  @memo[n] = result
end

until (n = $<.gets.to_i).zero?
  days = Rational(count(n), 10).ceil
  puts Rational(days, 365).ceil
end

0169 Blackjack

def calc(hand)
  i = hand.count(1)
  hand = hand - [1]
  point = 0
  while (a = hand.pop)
    point += case a
             when 2..9 then a
             else 10
             end
  end
  point1 = point2 = point + i
  point2 = point + 10 + i if i > 0
  if point2 <= 21
    point2
  elsif point1 <= 21
    point1
  else
    0
  end
end

until (n = $<.gets.chomp) == "0"
  puts calc(n.split.map(&:to_i))
end