Skip to content

Instantly share code, notes, and snippets.

@fabioyamate
Created Apr 27, 2014
Embed
What would you like to do?
Google Code Jam 2014 Round 1A
require 'scanf'
def flip(mask, os)
os.map { |o| mask ^ o }
end
Infinity = 1.0/0
def solve(n, l, flows, required_flows)
outlets = flows.split(" ").map { |f| f.to_i(2) }
outlet = outlets.first
required_outlets = required_flows.split(" ").map { |f| f.to_i(2) }
flips_done = required_outlets.reduce(Infinity) do |best_flips, possible_outlet|
flips = outlet ^ possible_outlet
left = flip(flips, outlets) - required_outlets
if left.empty?
new_flips_count = flips.to_s(2).scan(/\d/).select { |d| d == "1" }.size
if new_flips_count.zero? # best result possible
return 0
else
new_flips_count < best_flips ? new_flips_count : best_flips
end
else
best_flips
end
end
flips_done == Infinity ? "NOT POSSIBLE" : flips_done
end
input = ARGF.each_line.to_a
cases = input.shift.to_i
cases.times do |i|
n, l = input.shift.scanf("%d %d")
flow = input.shift
required_flow = input.shift
puts "Case ##{i+1}: #{solve(n, l, flow, required_flow)}"
end
# ruby shota.rb < input.in > output.in
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment