Problem:


Score : 800 points

Problem Statement

For a positive integer n, we denote the integer obtained by reversing the decimal notation of n (without leading zeroes) by rev(n). For example, rev(123) = 321 and rev(4000) = 4.

You are given a positive integer D. How many positive integers N satisfy rev(N) = N + D?

Constraints

D is an integer.

1 ≤ D < 10^9

Input

Input is given from Standard Input in the following format:

D

Output

Print the number of the positive integers N such that rev(N) = N + D.

Sample Input 1

63

Sample Output 1

2

There are two positive integers N such that rev(N) = N + 63: N = 18 and 29.

Sample Input 2

75

Sample Output 2

0

There are no positive integers N such that rev(N) = N + 75.

Sample Input 3

864197532

Sample Output 3

1920



Sample input:
63


Sample output:
2

Submission status: Wrong Answer

Solution code:
D = int(input())

def table(i, k):
    if i == k:
        return list(range(9, -1, -1)) + [0]*9
    else:
        return list(range(10, 0, -1)) + list(range(1, 10))

def nine(i):
    return 10**i - 1

def rec(d, i, k):
    res = 0
    num  = table(i, k)
    if i == 1:
        for j in range(-9, 10):
            if 9*j == d:
                return num[j]
        return 0
    if i == 2:
        for j in range(-9, 10):
            if d == 99*j:
                return 10*num[j]
    if not -10*nine(i) <= d <= 10*nine(i):
        return 0
    for j in range(-9, 10):
        if d%10 == j*nine(i)%10:
            res += num[j] * rec((d-j*nine(i))//10, i-2, k)
    return res

l = 0
while D % 10 == 0:
    D//= 10
    l += 1

if l == 0:
    a = 1
else:
    a = 9*10**(l-1)

ans = 0
for i in range(1, 13):
    if not l:
        ans += rec(D, i, i)
    else:
        ans += rec(D, i, 100)
print(a * ans)

Submission status: Wrong Answer

Solution code:
import math

diff = int(raw_input())

res = 0

for digits in range(1, 20):
	A = [0 for i in range(digits)]

	r = digits - 1
	l = 0

	ite = 0

	while l < r:
		A[ite] = 10**r - 10**l
		ite += 1
		l += 1
		r -= 1

	bonus = 1
	if l == r:
		bonus = 10

	ways_in_pos_0 = [0 for i in range(20)]
	ways_in_other = [0 for i in range(20)]

	for i in range(0, 10):
		for j in range(0, 10):
			ways_in_other[i - j] += 1
	for i in range(1, 10):
		for j in range(1, 10):
			ways_in_pos_0[i - j] += 1

	def recurse(pos, made):
		if pos == ite:
			if made == diff:
				return 1
			else:
				return 0
		elif pos == 0:
			curr = 0

			for i in range(-9, 9 + 1):
				if abs(made + i * A[pos] - diff) <= abs(made - diff):
					curr += recurse(pos + 1, made + i * A[pos]) * ways_in_pos_0[i]

			return curr
		else:
			curr = 0

			for i in range(-9, 9 + 1):
				if abs(made + i * A[pos] - diff) <= abs(made - diff):
					curr += recurse(pos + 1, made + i * A[pos]) * ways_in_other[i]

			return curr

	res += bonus * recurse(0, 0)

print res

Submission status: Wrong Answer

Solution code:
import math

diff = int(raw_input())

old_digits = int(math.floor((math.log10(diff))) + 1)

changed = True

res = 0

for digits in range(old_digits, old_digits * 2 + 2):
	A = [0 for i in range(digits)]

	r = digits - 1
	l = 0

	ite = 0

	while l < r:
		A[ite] = 10**r - 10**l
		ite += 1
		l += 1
		r -= 1

	bonus = 1
	if l == r:
		bonus = 10

	ways_in_pos_0 = [0 for i in range(20)]
	ways_in_other = [0 for i in range(20)]

	for i in range(0, 10):
		for j in range(0, 10):
			ways_in_other[i - j] += 1
	for i in range(1, 10):
		for j in range(1, 10):
			ways_in_pos_0[i - j] += 1

	def recurse(pos, made):
		if pos == ite:
			if made == diff:
				return 1
			else:
				return 0
		elif pos == 0:
			curr = 0

			for i in range(-9, 9 + 1):
				if abs(made + i * A[pos] - diff) <= abs(made - diff):
					curr += recurse(pos + 1, made + i * A[pos]) * ways_in_pos_0[i]

			return curr
		else:
			curr = 0

			for i in range(-9, 9 + 1):
				if abs(made + i * A[pos] - diff) <= abs(made - diff):
					curr += recurse(pos + 1, made + i * A[pos]) * ways_in_other[i]

			return curr

	res += bonus * recurse(0, 0)

print res

Submission status: Wrong Answer

Solution code:
import math

diff = int(raw_input())

digits = int(math.log10(diff)) + 1

A = [0 for i in range(digits)]

r = digits - 1
l = 0

ite = 0

while l < r:
	A[ite] = 10**r - 10**l
	ite += 1
	l += 1
	r -= 1

bonus = 1
if l == r:
	bonus = 10

ways_in_pos_0 = [0 for i in range(20)]
ways_in_other = [0 for i in range(20)]

for i in range(0, 10):
	for j in range(0, 10):
		ways_in_other[i - j] += 1
for i in range(1, 10):
	for j in range(1, 10):
		ways_in_pos_0[i - j] += 1

def recurse(pos, made):
	if pos == ite:
		if made == diff:
			return 1
		else:
			return 0
	elif pos == 0:
		curr = 0

		for i in range(-9, 9 + 1):
			curr += recurse(pos + 1, made + i * A[pos]) * ways_in_pos_0[i]

		return curr
	else:
		curr = 0

		for i in range(-9, 9 + 1):
			curr += recurse(pos + 1, made + i * A[pos]) * ways_in_other[i]

		return curr

print bonus * recurse(0, 0)

Submission status: Wrong Answer

Solution code:
D = int(input())
ans = 0
for i in range(1000000):
    if int(str(i)[::-1]) == i + D:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(d, K):
  r = 1
  for k in range(K,1,-2):
    if d >= 10**k:
      return 0
    t = (-d)%10
    d = abs((d-t*(10**(k-1)-1))//10)
    r *= 10-t-(K==k)
  return r*(10**(K%2)) if d == 0 else 0

D = int(input())
result = 0
l = len(str(D))
for k in range(l,2*l):
  result += solve(D, k)

print(result)

Submission status: Wrong Answer

Solution code:
# (10-x) ways: (0,x)-(9-x,9) -> (x, -x)           <- This should never happens when D > 0
# (x) ways:    (10-x,0)-(9,x-1) -> (x-10, 10 - x)

def solve(d, k, outer):
  if k <= 1:
    return 10**k if d == 0 else 0
  # if d >= 10**k:
  #   return 0

  t = d%10
  x = 10 - t
  d -= x*10**(k-1) - x
  return (t-outer)*solve(abs(d//10), k-2, 0)

D = int(input())
result = 0
for k in range(1,20):
  result += solve(D, k, 1)

print(result)

Submission status: Wrong Answer

Solution code:
def solve(d, k, outer):
  if k <= 1:
    return 10**k if d == 0 else 0
  if d >= 10**k:
    return 0

  tail = d % 10
  d -= (10-tail)*10**(k-1) + tail
  d = abs(d//10 + 1)
  return (tail-outer)*solve(d, k-2, 0)

D = int(input())
result = 0
for k in range(1,20):
  result += solve(D, k, 1)

print(result)

Submission status: Wrong Answer

Solution code:
# (10-x) ways: (0,x)-(9-x,9) -> (x, -x)
# (x) ways:    (10-x,0)-(9,x-1) -> (x-10, 10 - x)

def solve(d, k, outer):
  if k <= 1:
    return (10 - outer)**k if d == 0 else 0

  tail = d % 10
  if d >= 10**k:
    return 0
  c = d+tail*10**(k-1)
  return (10-tail-outer)*solve(abs(c//10), k-2, 0) + (tail-outer)*solve(abs((c-10**k)//10 + 1), k-2, 0)

D = int(input())
result = 0
l = len(str(D))
for k in range(1,20):
  result += solve(D, k, 1)

print(result)

Submission status: Wrong Answer

Solution code:
# (10-x) ways: (0,x)-(9-x,9) -> (x, -x)
# (x) ways:    (10-x,0)-(9,x-1) -> (x-10, 10 - x)

def solve(d, k, outer):
  if k <= 1:
    return (10 - outer)**k if d == 0 else 0

  tail = d % 10
  if d >= 10**k:
    return 0
  c = d+tail*10**(k-1)
  return (10-tail-outer)*solve(abs(c//10), k-2, 0) + (tail-outer)*solve(abs((c-10**k)//10 + 1), k-2, 0)

D = int(input())
result = 0
for k in range(1,20):
  result += solve(D, k, 1)
  print(k,result)

print(result)

Submission status: Wrong Answer

Solution code:
# (10-x) ways: (0,x)-(9-x,9) -> (x, -x)
# (x) ways:    (10-x,0)-(9,x-1) -> (x-10, 10 - x)

def solve(d, k, outer):
  if k <= 1:
    return (10 - outer)**k if d == 0 else 0

  tail = d % 10
  if d >= 10**k:
    return 0

  c = d+tail*10**(k-1)
  return (10-tail-outer)*solve(abs(c//10), k-2, 0) + (tail-outer)*solve(abs((c-10**k)//10 + 1), k-2, 0)

D = int(input())
result = 0
l = len(str(D))
for k in range(l,2*l+1):
  result += solve(D, k, 1)

print(result)

Submission status: Wrong Answer

Solution code:


# (10-x) ways: (0,x)-(9-x,9) -> (-x, x)
# (x) ways:    (10-x,0)-(9,x-1) -> (10-x, -10 + x)

def solve(D):

  leading_zeros = 0
  while D[-1] == 0:
    D.pop()
    leading_zeros += 1

  r = 1
  if len(D) >= 2:
    h,t = D.popleft(), D.pop()
    c = h + t

    if not D:
      r = t - (leading_zeros == 0) if c == 9 else 0
    elif 9 <= c <= 10:
      r = t - (leading_zeros == 0)
      c -= 10
      D[0] += c*10
      D[-1] += 1
      i = len(D)-1
      while i > 0 and D[i] == 10:
        D[i] = 0
        D[i-1] += 1
        i -= 1

  while len(D) > 2:
    h,t = D.popleft(), D.pop()
    c = h + t

    if -1 <= c <= 0:
      r *= 10-t
      D[0] += c*10
    elif 9 <= c <= 10:
      r *= t
      c -= 10
      D[0] += c*10
      D[-1] += 1
      i = len(D)-1
      while i > 0 and D[i] == 10:
        D[i] = 0
        D[i-1] += 1
        i -= 1
    else:
      r = 0
      D.clear()

  if len(D) == 2:
    h,t = D.popleft(), D.pop()
    c = h + t
    if c == 0:
      r *= 10 - t
    elif c == 9:
      r *= t
    else:
      r = 0

  if len(D) == 1:
    r *= 10 if D[0] == 0 else 0

  if r != 0 and leading_zeros > 0:
    r *= 9
    r *= 10**(leading_zeros-1)

  return r


from collections import deque
from random import randint


D = deque(map(int,input()))
r = solve(deque(D))

Q = deque(D)
for d in D:
  Q.appendleft(0)
  temp = solve(deque(Q))
  r += temp

if r == 0:
  Q = deque(D)
  for d in D:
    Q.append(0)
    r = solve(deque(Q))
    if r != 0:
      break

print(r)


# N = 10000
# for s in range(N):


#   t1 = list(map(int,str(randint(1,10**9))))
#   t2 = t1[::-1]
#   d1 = sum(t1[i]*10**i for i in range(len(t1)))
#   d2 = sum(t2[i]*10**i for i in range(len(t2)))
#   d = abs(d1-d2)
#   if d == 0:
#     continue

#   #print(d)
#   D = deque(map(int,str(d)))

#   r = solve(D.copy())

#   Q = D.copy()
#   for d in D:
#     Q.appendleft(0)
#     r += solve(Q.copy())

#   if r == 0:
#     print('fail')

Submission status: Wrong Answer

Solution code:

def rec(d, outer = False):
  head, tail = d[-1], d[0]
  if len(d) == 0:
    return 1
  if len(d) == 1:
    return 10-outer if tail == 0 else 0

  # (10-tail) ways: (0,tail)-(9-tail,9) -> (-tail, tail)
  # (tail) ways:    (10-tail,0)-(9,tail-1) -> (10-tail, -10 + tail)

  t = head + tail
  if len(d) == 2:
    if t == 0:
      return 10-tail
    if t == 9:
      return tail-outer
    
  else:
    sub = d[1:-1]
    if -1 <= t <= 0:
      sub[-1] += t*10
      return (10-tail)*rec(sub)
    
    if 9 <= t <= 10:
      t -= 10
      sub[-1] += t*10
      sub[0] += 1
      i = 0
      while i < len(sub)-1 and sub[i] == 10:
        sub[i] = 0
        sub[i+1] += 1
      return (tail-outer)*rec(sub)

  return 0


D = list(map(int,input()))
D = D[::-1]

leading_zeros = 0
while D[leading_zeros] == 0:
  leading_zeros += 1
D = D[leading_zeros:]

r = rec(D, outer=True)
if r != 0 and leading_zeros > 0:
  r *= 9
  r = str(r)
  r += "0"*(leading_zeros-1)
print(r)

Submission status: Wrong Answer

Solution code:

def rec(d, outer = False):
  head, tail = d[-1], d[0]
  if len(d) == 0:
    return 1
  if len(d) == 1:
    return 10-outer if tail == 0 else 0

  # (10-tail) ways: (0,tail)-(9-tail,9) -> (-tail, tail)
  # (tail) ways:    (10-tail,0)-(9,tail-1) -> (10-tail, -10 + tail)

  t = head + tail
  if len(d) == 2:
    if t == 0:
      return 10-tail
    if t == 9:
      return tail-outer
    else:
      return 0
    
  else:
    sub = d[1:-1]
    if -1 <= t <= 0:
      sub[-1] += t*10
      return (10-tail)*rec(sub)
    elif 9 <= t <= 10:
      t -= 10
      sub[-1] += t*10
      sub[0] += 1
      return (tail-outer)*rec(sub)
    else:
      return 0


D = list(map(int,input()))
D = D[::-1]

leading_zeros = 0
while D[leading_zeros] == 0:
  leading_zeros += 1
D = D[leading_zeros:]

r = rec(D, outer=True)
if r != 0 and leading_zeros > 0:
  r *= 9
  r = str(r)
  r += "0"*(leading_zeros-1)
print(r)

Submission status: Wrong Answer

Solution code:
def result(letters, number, cant_zero):
    if letters <= 1:
        if number == 0:
            return 10 ** letters
        return 0
    diff = 10 - number%10
    variants = number % 10 - cant_zero
    if number % 10 == 0:
        variants = 10 - cant_zero
    number -= diff * (10**(letters-1) - 1)
    number  = abs(number // 10)
    return variants * result(letters-2, number, 0)

d = int(input())
ans = 0
for i in range(20):
    ans += result(i, d, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
def recursion(length, ll, strisng, cc):
    answer = 0
    az = 0
    if ll * 2 < length:
        for i in range(10):
            string1 = strisng + str(i)
            line = recursion(length, ll+1, string1, cc)
            answer += line[0]
            az += line[1]
        line = [answer, az]
        return line        
    else:
        number = str(int(strisng) + int(cc[-ll:]))
        ds = ""
        for i in range(length // 2):
            if i + 1 <= len(number):
                ds += number[-i-1]
            else:
                ds += "0"
        strisng = ds + strisng
        if str(int(strisng) + int(cc)) == strisng[::-1] and strisng[0] != "0":
            answer += 1
        elif str(int(strisng) + int(cc)) == strisng[::-1]:
            az += 1
        line = [answer, az]
        return line
            
 
d = input()
d1 = d
plus = 0
while True:
    if d[-1] == "0":
        d = d[:-1]
        plus += 1
    else:
        break
l1 = recursion(len(d), 0, "", d)
l2 = recursion(len(d)+1, 0, "", d)
answer = l1[0] + l2[0]
az = l1[1] + l2[1]
yes = False
while plus > 0:
    yes = True
    if plus == 1:
        plus -= 1
        answer = answer * 9
        az = az * 9
    else:
        plus -= 1
        answer *= 10
        az *= 10
if yes:
    answer += az
print(answer)

Submission status: Wrong Answer

Solution code:
def recursion(length, ll, string, cc):
    answer = 0
    az = 0
    if ll * 2 < length:
        for i in range(10):
            string1 = string + str(i)
            line = recursion(length, ll+1, string1, cc)
            answer += line[0]
            az += line[1]
        line = [answer, az]
        return line        
    else:
        number = str(int(string) + int(cc[-ll:]))
        ds = ""
        for i in range(length // 2):
            if i + 1 <= len(number):
                ds += number[-i-1]
            else:
                ds += "0"
        string = ds + string
        if str(int(string) + int(cc)) == string[::-1] and string[0] != "0":
            answer += 1
        elif str(int(string) + int(cc)) == string[::-1]:
            az += 1
        line = [answer, az]
        return line
            

d = input()
d1 = d
plus = 0
while True:
    if d[-1] == "0":
        d = d[:-1]
        plus += 1
    else:
        break
l1 = recursion(len(d), 0, "", d)
l2 = recursion(len(d)+1, 0, "", d)
answer = l1[0] + l2[0]
az = l1[1] + l2[1]
yes = False
while plus > 0:
    yes = True
    if plus == 1:
        plus -= 1
        answer = answer * 9
        az = az * 9
    else:
        plus -= 1
        answer *= 10
        az *= 10
if yes:
    answer += az
print(answer)

Submission status: Wrong Answer

Solution code:
def recursion(length, ll, string, cc):
    if ll * 2 < length:
        for i in range(10):
            string1 = string + str(i)
            recursion(length, ll+1, string1, cc)
    else:
        number = str(int(string) + int(cc[-ll:]))
        ds = ""
        for i in range(length // 2):
            if i + 1 <= len(number):
                ds += number[-i-1]
            else:
                ds += "0"
        string = ds + string
        if str(int(string) + int(cc)) == string[::-1] and string[0] != "0":
            global answer
            answer += 1
        elif str(int(string) + int(cc)) == string[::-1]:
            global az
            az += 1
            

d = input()
d1 = d
plus = 0
while True:
    if d[-1] == "0":
        d = d[:-1]
        plus += 1
    else:
        break
answer = 0
az = 0
recursion(len(d), 0, "", d)
recursion(len(d)+1, 0, "", d)
yes = False
while plus > 0:
    yes = True
    if plus == 1:
        plus -= 1
        answer = answer * 9
        az = az * 9
    else:
        plus -= 1
        answer *= 10
        az *= 10
if yes:
    answer += az
print(answer)

Submission status: Wrong Answer

Solution code:
def recursion(length, ll, string, cc):
    if ll * 2 < length:
        for i in range(10):
            string1 = string + str(i)
            recursion(length, ll+1, string1, cc)
    else:
        number = str(int(string) + int(cc[-ll:]))
        ds = ""
        for i in range(length // 2):
            if i + 1 <= len(number):
                ds += number[-i-1]
            else:
                ds += "0"
        string = ds + string
        if str(int(string) + int(cc)) == string[::-1] and string[0] != "0":
            global answer
            answer += 1
        elif str(int(string) + int(cc)) == string[::-1]:
            global az
            az += 1
            

d = input()
d1 = d
plus = 0
while True:
    if d[-1] == "0":
        d = d[:-1]
        plus += 1
    else:
        break
answer = 0
az = 0
recursion(len(d), 0, "", d)
recursion(len(d)+1, 0, "", d)
yes = False
while plus > 0:
    yes = True
    if plus == 1:
        plus -= 1
        answer = answer * 9
        az = az * 9
    else:
        plus -= 1
        answer *= 10
        az *= 9
if yes:
    answer += az
print(answer)

Submission status: Wrong Answer

Solution code:
def recursion(length, ll, string, cc):
    if ll * 2 < length:
        for i in range(10):
            string1 = string + str(i)
            recursion(length, ll+1, string1, cc)
    else:
        number = str(int(string) + int(cc[-ll:]))
        ds = ""
        for i in range(length // 2):
            if i + 1 <= len(number):
                ds += number[-i-1]
            else:
                ds += "0"
        string = ds + string
        if str(int(string) + int(cc)) == string[::-1] and string[0] != "0":
            global answer
            answer += 1
        elif str(int(string) + int(cc)) == string[::-1]:
            global az
            az += 1
            

d = input()
d1 = d
plus = 0
while True:
    if d[-1] == "0":
        d = d[:-1]
        plus += 1
    else:
        break
answer = 0
az = 0
recursion(len(d), 0, "", d)
recursion(len(d)+1, 0, "", d)
yes = False
while plus > 0:
    yes = True
    if plus == 1:
        plus -= 1
        answer = answer * 9
        az = az * 9
    else:
        plus -= 1
        answer *= 10
        az *= 9
if yes:
    answer += az

Submission status: Wrong Answer

Solution code:
def recursion(length, ll, string, cc):
    if ll * 2 < length:
        for i in range(10):
            string1 = string + str(i)
            recursion(length, ll+1, string1, cc)
    else:
        number = str(int(string) + int(cc[-ll:]))
        ds = ""
        for i in range(length // 2):
            if i + 1 <= len(number):
                ds += number[-i-1]
            else:
                ds += "0"
        string = ds + string
        if str(int(string) + int(cc)) == string[::-1] and string[0] != "0":
            global answer
            answer += 1
            

d = input()
plus = 0
while True:
    if d[-1] == "0":
        d = d[:-1]
        plus += 1
    else:
        break
answer = 0
recursion(len(d), 0, "", d)
recursion(len(d)+1, 0, "", d)
while plus > 0:
    plus -= 1
    answer *= 10
print(answer)

Submission status: Wrong Answer

Solution code:
def recursion(length, ll, string, cc):
    if ll * 2 < length:
        for i in range(10):
            string1 = string + str(i)
            recursion(length, ll+1, string1, cc)
    else:
        number = str(int(string) + int(cc[-ll:]))
        ds = ""
        for i in range(length // 2):
            if i + 1 <= len(number):
                ds += number[-i-1]
            else:
                ds += "0"
        string = ds + string
        if str(int(string) + int(cc)) == string[::-1] and string[0] != "0":
            global answer
            answer += 1
            

d = input()
plus = 0
while True:
    if d[-1] == "0":
        d = d[:-1]
        plus += 1
    else:
        break
answer = 0
recursion(len(d), 0, "", d)
recursion(len(d)+1, 0, "", d)
while plus > 0:
    if plus == 1:
        plus -= 1
        answer = answer * 9
    else:
        plus -= 1
        answer *= 10
print(answer)

Submission status: Wrong Answer

Solution code:
n = (int)(input(""))
Pow = []
Pow.append(1)
Pow.append(1)
for i in range (2, 100):
    Pow.append(Pow[i - 1] * 10)
s = n
sum = 0
for i in range(2, 100):
	s = n
	tmp = 1
	k = (i + 1) / 2
	for j in range(i, k, -1):
		t = Pow[j] - Pow[i - j + 1]
		kk = s / t
		less = 0
		if i == j: less = 9 - kk
		else: less = 10 - kk
		if less <= 0: break
		tmp *= less
		s -= kk * t
	if i % 2 == 1:
		tmp *= 10
	if s != 0:
		tmp = 0
	sum += tmp
print sum

Submission status: Wrong Answer

Solution code:
n = (int)(input(""))
Pow = []
Pow.append(1)
Pow.append(1)
for i in range (2, 100):
    Pow.append(Pow[i - 1] * 10)
s = n
sum = 0
for i in range(2, 100):
	s = n
	tmp = 1
	k = (i + 1) / 2
	for j in range(i, k, -1):
		t = Pow[j] - Pow[i - j + 1]
		if s < t:
			tmp *= 9 + (int)(i != j)
		else:
			kk = s / t
			if kk >= 9 + (i != j): break
			tmp *= 9 - (kk) + (i != j)
			s -= kk * t
	if i % 2 == 1:
		tmp *= 10
	if s != 0:
		tmp = 0
	sum += tmp
print sum

Submission status: Wrong Answer

Solution code:
n = (int)(input(""))
Pow = []
Pow.append(1)
Pow.append(1)
for i in range (2, 100):
    Pow.append(Pow[i - 1] * 10)
s = n
sum = 0
for i in range(2, 100):
	s = n
	tmp = 1
	k = (i + 1) / 2
	for j in range(i, k, -1):
		t = Pow[j] - Pow[i - j + 1]
		if s < t:
			tmp *= 9 + (int)(i != j)
		else:
			kk = s / t
			if kk >= 10: break
			tmp *= 9 - (kk) + (i != j)
			s -= kk * t
	if i % 2 == 1:
		tmp *= 10
	if s != 0:
		tmp = 0
	sum += tmp
print sum

Submission status: Wrong Answer

Solution code:
n = (int)(input(""))
Pow = []
Pow.append(1)
Pow.append(1)
for i in range (2, 100):
    Pow.append(Pow[i - 1] * 10)
s = n
sum = 0
for i in range(2, 100):
	s = n
	tmp = 1
	k = (i + 1) / 2
	for j in range(i, k, -1):
		t = Pow[j] - Pow[i - j + 1]
		if s < t:
			tmp *= 9 + (int)(i != j)
		else:
			kk = s / t
			less = 10 - kk - (i == j)
			if less <= 0:
				break
			else:
				tmp *= less
			s -= kk * t
	if i % 2 == 1:
		tmp *= 10
	if s != 0:
		tmp = 0
	sum += tmp
print sum

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

def f(i,d):
    """
    i 桁の n で、r(n)-n = d
    """
    n = i-1
    m = 0
    res = []
    while n>m:
        x = 10**n-10**m
        if m:
            res.append(tuple((x*k,v) for k,v in d2.items()))
        else:
            res.append(tuple((x*k,v) for k,v in d1.items()))
        n -= 1
        m += 1
    
    def sums(lsts):
        dic = {0:1}
        for lst in lsts:
            ndic = {}
            for k1,v1 in dic.items():
                for k2,v2 in lst:
                    k = k1+k2
                    v = v1*v2
                    if k in ndic: ndic[k] += v
                    else: ndic[k] = v
            dic = ndic
        
        return dic.items()
    
    L = len(res)
    #print(res[L//2:])
    s1 = sums(res[:L//2])
    s2 = sorted(sums(res[L//2:]))
    
    #print(s1)
    #print(s2)
    #print(d)

    v = 0
    from bisect import bisect_left
    for k1,v1 in s1:
        idx = bisect_left(s2,(d-k1,0))
        if idx < len(s2) and s2[idx][0] == d-k1:
            #print(k1,v1,idx,s2[idx])
            v += v1*s2[idx][1]
    return v*(1 if i%2==0 else 10)


d, = map(int,read().split())

ans = 0

from collections import Counter

d1 = Counter()
for i in range(10):
    for j in range(1,10):
        d1[i-j] += 1
        
d2 = Counter()
for i in range(10):
    for j in range(10):
        d2[i-j] += 1

for i in range(2,19):
#for i in range(2,19):
    r = f(i,d)    
    #print(r,i)
    ans += r

print(ans)

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/arc075/tasks/arc075_d

桁数を決め打ちする？
 abcd
-dcba
 ABCD

999a+90b-90c-999d = ABCD

みたいな感じになる
これをいい感じに満たせばおk
aとd,bとcをまとめる
-9～9の19通り


19**4 = 2476099通り
aとdの分配の仕方の通り数をあらかじめ数えておけばおｋ
ただし、a != 0
差は、9999109999
      9999019999
差があるとDを超える場合は探索を打ち切ればおｋ

"""
import sys

def dfs(dig,nd,nsum):

    P = 10**((dig-1)-nd) - 10**nd #この桁の寄与の基準
    maxc = 10**((dig-1)-nd)
    
    if nd == dig//2:
        if nsum == D:
            if dig % 2 == 0:
                return 1
            else:
                return 10
        return 0
    elif nd != 0:
        ret = 0
        for i in range(-9,10):
            if nsum+P*i < D-maxc or nsum+P*i > D+maxc:
                continue
            ret += dfs(dig,nd+1,nsum+P*i) * sums[i]
        #print (ret,"y")
        return ret
    else:
        ret = 0
        for i in range(-9,10):
            if nsum+P*i < D-maxc or nsum+P*i > D+maxc:
                continue
            tmp = dfs(dig,nd+1,nsum+P*i) * sums_z[i]
            #if tmp > 0:
            #    print (dig,nd+1,i,"is 1",tmp)
            ret += tmp
        return ret
            

D = int(input())
ans = 0
sums = [0] * 30
for i in range(-9,10):
    for x in range(-9,1):
        for y in range(0,10):
            if x+y == i:
                sums[i] += 1
print (sums , file=sys.stderr)
sums_z = [0] * 30
for i in range(-9,10):
    for x in range(-9,0):
        for y in range(1,10):
            if x+y == i:
                sums_z[i] += 1
print (sums_z , file=sys.stderr)

for dig in range(1,20):

    now = dfs(dig,0,0)
    #print (dig,now)
    ans += now

print (ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


d = int(input())
def main(d):
    from collections import defaultdict
    vals = defaultdict(int)
    vals2 = defaultdict(int)
    for i in range(10):
        for j in range(10):
            vals[i-j] += 1
            if j>0:
                vals2[i-j] += 1
    def sub(n):
        vs = []
        for i in range(n):
            if i>=n-i:
                break
            vs.append(pow(10,n-i) - pow(10,i))
    #     if 9*sum(vs)<d:
    #         return 0
        def _sub(val, i):
            """vs[i:]以降でvalを作る通り数
            """
            if i==len(vs):
                if val==0:
                    return 1
                else:
                    return 0
            ans = 0
            for j in range(-9, 10):
                if (vs[i]*j)%pow(10,i+1)==val%(pow(10,i+1)):
                    ans += _sub(val-vs[i]*j, i+1) * vals[j]
            return ans

        ans = 0
        for i in range(-9,10):
            if (vs[0]*i)%10==d%10:
                ans += _sub(d-vs[0]*i, 1) * vals2[i]
        if n%2==0:
            ans *= 10
        return ans
    ans = 0
    i = 1
    while True:
        val = sub(i)
        ans += val
        if i>20:
            break
    #     if pow(10,i)-1>d:
    #         break
        i += 1
    return ans
print(main(d))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

def f(i,d):
    """
    i 桁の n で、r(n)-n = d
    """
    n = i-1
    m = 0
    res = []
    while n>m:
        x = 10**n-10**m
        if m:
            res.append(tuple((x*k,v) for k,v in d2.items()))
        else:
            res.append(tuple((x*k,v) for k,v in d1.items()))
        n -= 1
        m += 1
    
    def sums(lsts):
        dic = {0:1}
        for lst in lsts:
            ndic = {}
            for k1,v1 in dic.items():
                for k2,v2 in lst:
                    k = k1+k2
                    v = v1*v2
                    if k in ndic: ndic[k] += v
                    else: ndic[k] = v
            dic = ndic
        
        return dic.items()
    
    L = len(res)
    #print(res[L//2:])
    s1 = sums(res[:L//2])
    s2 = sorted(sums(res[L//2:]))
    
    #print(s1)
    #print(s2)
    #print(d)

    v = 0
    from bisect import bisect_left
    for k1,v1 in s1:
        idx = bisect_left(s2,(d-k1,0))
        if idx < len(s2) and s2[idx][0] == d-k1:
            #print(k1,v1,idx,s2[idx])
            v += v1*s2[idx][1]
    return v*(1 if i%2==0 else 10)


d, = map(int,read().split())

ans = 0

from collections import Counter

d1 = Counter()
for i in range(10):
    for j in range(1,10):
        d1[i-j] += 1
        
d2 = Counter()
for i in range(10):
    for j in range(10):
        d2[i-j] += 1

for i in range(2,18):
#for i in range(2,19):
    r = f(i,d)    
    #print(r,i)
    ans += r
if d%(10**9-10**8)==0:
    r = d//(10**9-10**8)
    ans += d2[r]*(10**7)*9

print(ans)