Submission #162824

---

Source Code Expand

def solve_naive(n)
  (1...n).count {|x| /[49]/ =~ x.to_s }
end

# 0 <= x < 10^k
@memo = []
def g(k)
  if k == 0
    0
  else
    @memo[k] ||= 2 * (10**(k-1)) + 8 * g(k-1)
  end
end

# 0 <= x < m * 10^k
def h(m,k)
  case m
  when 1, 2, 3, 4
    m * g(k)
  when 5, 6, 7, 8, 9
    (m - 1) * g(k) + 10**k
  end
end

def hh(m,k) [h(m,k), solve_naive(m*10**k)] end

def solve(n)
  return 0 if n == 0
  digits = n.to_s.chars.to_a
  k = digits.size - 1
  car, cdr = digits.first.to_i, digits.drop(1).join("").to_i
  case car
  when 1, 2, 3, 5, 6, 7, 8
    h(car,k) + solve(cdr)
  when 4, 9
    h(car,k) + (n-car*10**k)
  when 0
    solve(cdr)
  end
end

if $0 == __FILE__
  a, b = gets.split(" ").map(&:to_i)
  puts solve(b) - solve(a)
end

Submission Info

Judge Result