GCJ 2012 Round 1A - A. Password Problem

A.rb

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