AOJ（問題集）1

AIZU ONLINE JUDGE: Programming Challenge
　

0000 QQ

9.times do |i|
  9.times {|j| puts "#{x = i + 1}x#{y = j + 1}=#{x * y}"}
end

0001 List of Top 3 Hills

puts $<.readlines.map(&:to_i).sort {|a, b| b <=> a}.take(3)

0002 Digit Number

$<.readlines.each do |l|
  puts Math.log10(l.split.map(&:to_i).sum).to_i + 1
end

0003 Is it a Right Triangle?

$<.readlines.drop(1).each do |l|
  a, b, c = l.split.map(&:to_i).sort
  puts((a * a + b * b == c * c) ? "YES" : "NO")
end

0004 Simultaneous Equation

$<.readlines.each do |l|
  a, b, c, d, e, f = l.split.map(&:to_i)
  r = a * e - b * d
  x = (c * e - b * f) / r.to_f
  y = (a * f - c * d) / r.to_f
  x = x.abs if x == 0
  y = y.abs if y == 0
  printf("%.3f %.3f\n", x, y)
end

0005 GCD and LCM

$<.readlines.each do |l|
  a, b = l.split.map(&:to_i)
  puts "#{a.gcd(b)} #{a.lcm(b)}"
end

0006 Reverse Sequence

puts $<.gets.chomp.reverse

0007 Debt Hell

debt = 10_0000
$<.gets.to_i.times do
  debt = debt * 1.05
  debt = (debt / 1000).ceil * 1000
end
puts debt

0008 Sum of 4 Integers

require 'set'

$<.readlines.map(&:to_i).each do |n|
  s = Set.new
  l = n / 4
  l = (l < 10) ? l : 9
  (0..l).each do |a|
    (a..9).each do |b|
      (b..9).each do |c|
        d = n - a - b - c
        if c <= d and d <= 9
          s += [a, b, c, d].permutation.to_a
        end 
      end
    end
  end
  puts s.size
end

これで 0.28秒。

$<.readlines.map(&:to_i).each do |n|
  co = 0
  10.times do |a|
    10.times do |b|
      10.times do |c|
        10.times do |d|
          co += 1 if a + b + c + d == n
        end
      end
    end
  end
  puts co
end

これで 0.09秒。わざわざ工夫しないほうが速かった。
　

0009 Prime Number

$<.readlines.map(&:to_i).each do |n|
  ar = (0..n).to_a
  2.upto(Math.sqrt(n).to_i) do |i|
    next if ar[i].zero?
    2.upto(n / i) {|j| ar[i * j] = 0}
  end
  co = 0
  ar[2..-1].each {|i| co += 1 if i.nonzero?}
  puts co
end

4.04秒もかかってしまった。

N = 999_999
ar = [*0..N]
2.upto(Math.sqrt(N).to_i) do |i|
  next if ar[i].zero?
  2.upto(N / i) {|j| ar[i * j] = 0}
end

$<.readlines.map(&:to_i).each do |n|
  co = 0
  ar[2..-1].each do |i|
    break if i > n
    co += 1 if i.nonzero?
  end
  puts co
end

よく考えたらその都度ふるいを実行することはなかった。これでも 2.5秒。
　

0010 Circumscribed Circle of a Triangle

$<.readlines.drop(1).each do |l|
  x1, y1, x2, y2, x3, y3 = l.split.map(&:to_f)
  a = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)
  b1 = x1 * x1 + y1 * y1
  b2 = x2 * x2 + y2 * y2
  b3 = x3 * x3 + y3 * y3
  x = (b1 * (y2 - y3) + b2 * (y3 - y1) + b3 * (y1 - y2)) / (2 * a)
  y = (b1 * (x3 - x2) + b2 * (x1 - x3) + b3 * (x2 - x1)) / (2 * a)
  r = Math.sqrt((x - x1) ** 2 + (y - y1) ** 2)
  printf("%.3f %.3f %.3f\n", x, y, r)
end