Skip to content

Instantly share code, notes, and snippets.

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

Embed
What would you like to do?
GCJ 2012 Round 1A - A. Password Problem
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
# main
t_start = Time.now
# ここから問題に応じて
cases = readline().to_i
(1 .. cases).each do |case_index|
# readline().chomp
# readline().split
a, b = ris
p = rfs
# keep
all_ok = p.inject(:*)
keep = all_ok * (b - a + 1) + (1 - all_ok) * ((b - a) + 1 + b + 1)
ppd keep
# enter
enter = 1 + b + 1
ppd enter
# backspace
bs = []
p_cur = 1.0
for c in 1 .. a-1
p_cur *= p[c-1]
bs_count = a - c
left_ok = 1
if bs_count != a
left_ok = p_cur
else
left_ok = 1
end
ok_types = (bs_count + b - (a-bs_count) + 1)
bs_1 = left_ok * ok_types + (1 - left_ok) * (ok_types + b + 1)
bs << bs_1
end
ppd bs
answer = (bs + [keep, enter]).min
puts "Case ##{case_index}: #{answer}"
# 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.