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
