Skip to content

Instantly share code, notes, and snippets.

@mururu mururu/billboards.rb
Created Jan 25, 2012

Embed
What would you like to do?
Billboards - Facebook Hacker Cup 2012 Qualification Round
# coding: utf-8
class Billboards
def initialize(input)
lines = []
open(input) do |f|
lines = f.readlines.map{|l|l.chomp!}
end
@num = lines.shift.to_i
@case = []
lines.each_with_index do |line,i|
tokens = line.split
@case[i] = { :w => tokens.shift.to_i, :h => tokens.shift.to_i, :words => tokens }
end
end
def self.conc(co)
wls = co[:words].map{|word|word.length}
p max = [[co[:w]/(wls.max), co[:h]].max, Math.sqrt(co[:w]*co[:h]/wls.inject(:+)).to_i].min
(0..max).each do |i|
f = max + 1 - i
p overflow?(f,co[:w],co[:h],wls)
return f unless overflow?(f,co[:w],co[:h],wls)
end
end
def set_ans
@ans = @case.map{|v| p v; Billboards.conc v}
end
def put_ans(output)
self.set_ans
open(output, "w") do |f|
@ans.each_with_index do |ans, i|
p "Case #" + (i+1).to_s + ": " + ans.to_s
f.puts("Case #" + (i+1).to_s + ": " + ans.to_s)
end
end
end
attr_reader :num, :case, :ans
end
def overflow?(f,w,h,wls)
max_w = w / f
max_h = h / f
a = []
i = 0
wls.each do |wl|
if wl > max_w
return true
end
if a.last.nil? || (a.last + 1 + wl > max_w)
a << wl
i += 1
else
a[-1] += wl + 1
end
if i > max_h
return true
end
end
false
end
bill = Billboards.new(ARGV[0])
bill.put_ans(ARGV[1])
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.