Skip to content

Instantly share code, notes, and snippets.

@luikore

luikore/lucky tickets 1.rb

Last active Dec 18, 2015
Embed
What would you like to do?
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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment