Codeforces #84 Div2 D ("1 20 100 120 5" -> "0.2" on local, but "0.15" on site)

084d.rb

#!/usr/bin/env ruby

args = STDIN.gets.split(" ").map{|i| i.to_i}
argp = args[0..1]
argv = args[2..3]
argk = args[4]

min = [argp[0],argv[0]].min
max = [argp[1],argv[1]].max


digits = 1
num = [[4]*digits].join.to_i
arr = []
while num <= max
  init = [[4]*digits].join.to_i
  sevens = 0
  begin
    num = init + (sevens.to_s(2).to_i*3)
    if num <= max and min <= num
      arr << num
    end
    if num > max
      break
    end
    sevens += 1
  end while sevens <= digits+1
  digits += 1
end

if arr.length < argk
  puts 0.0
  exit
end

def update argp,argv,arr,argk
  ret=0.0
  arrlow = Marshal.load(Marshal.dump(argp))
  arrhigh = Marshal.load(Marshal.dump(argv))
  (0..(arr.length-argk)).each do |i|
    kmin = arr[i]
    kmax = arr[i+argk-1]
    if arrlow[0] <= kmin and kmax <= arrhigh[1]
      low  = [[arrlow[1],kmin].min - [arrlow[0],kmin].min + 1,0].max
      high = [[arrhigh[1],kmax].max - [arrhigh[0],kmax].max + 1, 0].max
      ret += low*high
      arrlow[0]  = kmin+1
      arrhigh[1] = kmax-1
    end
  end
  ret
end

ret = 0.0
ret += update(argp,argv,arr,argk)
ret += update(argv,argp,arr,argk)

puts ret*1.0/(argp[1] - argp[0] +1)/(argv[1]-argv[0]+1)