Skip to content

Instantly share code, notes, and snippets.

@nicklegr nicklegr/B.rb
Created May 1, 2012

Embed
What would you like to do?
GCJ 2012 Round 1A - B. Kingdom Rush
require 'pp'
# http://0xcc.net/ruby-bsearch/index.html.ja
# require './bsearch'
# https://github.com/kanwei/algorithms
# require 'rubygems'
# require 'algorithms'
# include Containers
def ppd(*arg)
if $DEBUG
pp(*arg)
end
end
def putsd(*arg)
if $DEBUG
puts(*arg)
end
end
def ri
readline.to_i
end
def ris
readline.split.map do |e| e.to_i end
end
def rs
readline.chomp
end
def rss
readline.chomp.split
end
def rfs
readline.split.map do |e| e.to_f end
end
def rws(count)
words = []
for i in 1 .. count
words << readline.chomp
end
words
end
MAX = 9999999
# main
t_start = Time.now
# ここから問題に応じて
cases = readline().to_i
(1 .. cases).each do |case_index|
n = ri
ab = []
for i in 1..n
ab << ris
end
failed = false
point = 0
tries = 0
loop do
raise if point > ab.size * 2
break if point == ab.size * 2
tries += 1
b_oks = ab.find_all do |e| e[1] <= point end
if b_oks.size != 0
target = b_oks.first
if target[0] != MAX
point += 2
else
point += 1
end
target[0] = MAX
target[1] = MAX
next
end
a_oks = ab.find_all do |e| e[0] <= point end
if a_oks.size != 0
a_oks.sort! do |a, b| b[1] <=> a[1] end
target = a_oks.first
point += 1
target[0] = MAX
next
end
failed = true
break
end
if failed
puts "Case ##{case_index}: Too Bad"
else
puts "Case ##{case_index}: #{tries}"
end
# progress
trigger =
if cases >= 10
case_index % (cases / 10) == 0
else
true
end
if trigger
STDERR.puts("case #{case_index} / #{cases}, time: #{Time.now - t_start} s")
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.