http://acm.timus.ru/problem.aspx?space=1&num=1044

lucky tickets 1.rb

def f n
  half = n / 2
  table = Hash.new 0
  ('0' * half).upto '9' * half do |s|
    sum = s.chars.map(&:to_i).inject(:+)
    table[sum] += 1
  end
  r = 0
  table.each do |_, v|
    r += v*v
  end
  r
end

p f $stdin.read.to_i

lucky tickets 2.rb

CACHE = {}

# count how many digit combinations for: rest digits added up to a sum
def g sum, rest
  CACHE[(sum << 8) | rest] ||= begin
    if rest == 1
      if sum <= 9
        1
      end
    else
      min = sum - (rest - 1) * 9
      min = 0 if min < 0
      max = sum > 9 ? 9 : sum
      r = 0
      rest -= 1
      min.upto max do |i|
        r += g(sum - i, rest)
      end
      r
    end
  end
end

def f n
  half = n / 2
  max = 9 * half
  middle = (max + 1) / 2
  r = 0
  0.upto max do |sum|
    v = g((sum <= middle ? sum : max - sum), half)
    r += v * v
  end
  r
end

p f $stdin.read.to_i