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