Codeforces Round #154 (Div. 2)
http://www.codeforces.com/contest/253/
A,B問題だけ。
A. Boys and Girls
少年(B)と少女(G)の数がそれぞれ与えられる。
できるかぎり異性が隣合うようにしながら一列にならべる。
$stdin = File.open("input.txt") $stdout = File.open("output.txt", "w") n, m = gets.chomp.split(" ").map{|n| n.to_i} if n == m puts "GB" * n elsif n > m puts "BG" * m + "B" * (n - m) else puts "GB" * n + "G" * (m - n) end
B. Physics Practical
与えられた配列cを、配列の最大値 <= 配列の最小値×2にならしたい。
上記の条件を満たすように配列cから取り除く要素数の最小値を求めよ。
n以下の要素を削除したときに、できるかぎり取りこぼしが少ない数を求めればいい。
$stdin = File.open("input.txt") $stdout = File.open("output.txt", "w") n = gets.chomp.to_i c = {} gets.chomp.split(" ").each do |n| key = n.to_i if c.has_key? key c[key] += 1 else c[key] = 1 end end field = Array.new(5000, 0) for i in 1 .. 5000 do field[i] = field[i - 1] + (c.has_key?(i) ? c[i] : 0) end ans = 99999 for i in 1 .. 2500 do ans = [ans, field[i - 1] + (field[5000] - field[i * 2])].min end puts ans