Skip to content

Instantly share code, notes, and snippets.

@andruby
Created May 8, 2010 23:27
Show Gist options
  • Save andruby/394833 to your computer and use it in GitHub Desktop.
Save andruby/394833 to your computer and use it in GitHub Desktop.
My solution to Google's CodeJam 2010
# Helper class for file I/O and time measurement
class Problem
def initialize(input_file,output_file=nil)
@output_file = output_file
@start_time = Time.now
@input_file = input_file
@output_file ||= input_file.gsub('.txt','').gsub('.in','.out')
File.delete(@output_file) if File.exists?(@output_file)
end
def solve_case(&block)
File.open(@input_file) do |input|
n = input.gets.to_i
puts "#{n} Cases\n"
1.upto(n) do |case_nr|
solution = yield(input)
puts "Case #{case_nr}, solution: #{solution}"
write_to_output(case_nr,solution)
end
end
terminate
end
def write_to_output(case_nr,solution)
File.open(@output_file,'a') { |f| f.puts "Case ##{case_nr}: #{solution}" }
end
def terminate
puts "\nTook: #{Time.now-@start_time} seconds"
end
end
# Needs 0.75 seconds for the large dataset on Ruby 1.9.1
require 'problem.rb'
problem = Problem.new("A-large.in.txt")
problem.solve_case do |input|
n, k = input.gets.strip.split(' ').collect { |x| x.to_i }
if ((k+1) % (2**n) == 0) then "ON" else "OFF" end
end
# Needs 0.06 seconds for the large dataset on Ruby 1.9.1
require 'problem.rb'
class Array
def sum
self.inject(0) { |sum, n| sum+n }
end
end
problem = Problem.new("C-large-practice.in.txt","v4.out")
problem.solve_case do |input|
r, k, n = input.gets.strip.split(' ').collect { |x| x.to_i }
g = input.gets.strip.split(' ').collect { |x| x.to_i }
raise "number of groups miscount g #{g.size} and n #{n}" if g.size != n
euros = 0
stop_pointer = 0
history = {}
ride_nr = 0
begin
# we're back where we once were
if history[stop_pointer]
# we've seen this before
prev_ride_nr, prev_euros = history[stop_pointer]
rides_in_between = ride_nr - prev_ride_nr
euros_made_in_between = euros - prev_euros
rides_left = r - ride_nr
# skip over (rides_left / rides_in_between) * rides_in_between
ride_nr += (rides_left / rides_in_between) * rides_in_between
euros += (rides_left / rides_in_between) * euros_made_in_between
break if ride_nr >= r
else
# store the position in history
history[stop_pointer] = [ride_nr, euros]
end
sum = 0
counter = 0
while (sum += g[stop_pointer]) <= k and (counter += 1) <= n
# Add the group to the coaster and move the pointer up
stop_pointer = (stop_pointer + 1) % n # wrap around pointer
end
# No more room or queue is empty (when counter < n)
# Register the ride
euros += sum - g[stop_pointer] # retract the last one
ride_nr += 1
end until ride_nr >= r
euros
end
# Needs 0.04 seconds for the large dataset on Ruby 1.9.1
require 'problem.rb'
problem = Problem.new("B-large-practice.in.txt")
problem.solve_case do |input|
n, *t = input.gets.strip.split(' ').collect { |x| x.to_i }
sorted = t.sort.uniq
prev = sorted.shift
differences = sorted.map { |x| ret = (x-prev).abs; prev=x; ret }
gcd = differences.first
differences.each { |x| gcd = x.gcd(gcd) }
rest = t.first % gcd
if rest == 0 then 0 else gcd - rest end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment