class Array

def rotate!

v = self.pop

self.unshift v

end

end

def convert_num(array, base)

digit = array.count - 1

array.inject(0) {|sum,d| sum += (d * base**digit) ; digit -= 1 ; sum}

end

def filter_and_convert_values(permutations, base, digits_c, num_c, zero_check)

perm = []

num_digits_c = digits_c.length

max_leading_zeros = nil

for digits in permutations

unless max_leading_zeros

max_leading_zeros = digits.count - num_digits_c

max_leading_zeros += 1 if digits_c[0, 1] == "1"

end

num = convert_num(digits, base)

next if num > num_c

if zero_check

leading_zeros = 0

for d in digits

break if d != 0

leading_zeros += 1

end

next if leading_zeros > max_leading_zeros

end

perm << num

end

perm

end

file = STDIN

test_cases = file.gets.to_i

test_cases.times do

line = file.gets

base, digits_a, digits_b, digits_c = line.split

base = base.to_i

digits_a = digits_a.split('').map{|e| e.to_i(base)}

digits_b = digits_b.split('').map{|e| e.to_i(base)}

num_c = digits_c.to_i(base)

# Auswaehlen, welche Werte Sinn machen (z.B. num_x <= num_c)!

min_digits = digits_c.length

min_digits -= 1 if digits_c[0, 1] == "1"

perm_a = filter_and_convert_values(digits_a.permutation, base, digits_c, num_c, digits_b.count < min_digits)

perm_b = filter_and_convert_values(digits_b.permutation, base, digits_c, num_c, digits_a.count < min_digits)

# Need to work around an Array.permutation bug which might yield twice

# the elements.

perm_a.sort!.uniq!

perm_b.sort!.uniq!

count = 0

for num_a in perm_a

for num_b in perm_b

count += 1 if num_a + num_b == num_c

end

end

puts count

end

__END__

5

2 10 10 11

3 2 2 11

10 101 12 23

10 10 100 1000

10 43716 70251864 71130699

## Comments

**Please login at the top to post a comment.**