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

Solution (Python):

"""

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]
        
        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]
            
            
            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)
    
    ans += now

print (ans)

Solution (Python):
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))
    
    
        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
    
    
        i += 1
    return ans
print(main(d))

Solution (Python):


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)
    
    s1 = sums(res[:L//2])
    s2 = sorted(sums(res[L//2:]))
    
    
    
    

    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:
            
            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):

    r = f(i,d)    
    
    ans += r
if d%(10**9-10**8)==0:
    r = d//(10**9-10**8)
    ans += d2[r]*(10**7)*9

print(ans)

Solution (Python):
D=int(input())
count=0
while D%10==0:
    count+=1
    D//=10
if not count:
    ans=0
    for i in range(1,1000):
        val=str(i)
        val=val[::-1]
        rev=int(val)
        if rev-i==D:
            ans+=1

    for d in range(4,18):
        dic1={}
        dic2={}
        if d%2==0:
            k=d//2
            l=k//2
            def dfs(n,a):
                if n==l:
                    val=0
                    res=1
                    for i in range(len(a)):
                        val+=a[i]*(10**(d-1-i)-10**i)
                        if i!=0:
                            res*=10-abs(a[i])
                        else:
                            res*=9-abs(a[i])
                    if val not in dic1:
                        dic1[val]=0
                    dic1[val]+=res
                    return 0

                for i in range(-9,10):
                    dfs(n+1,a+[i])

            dfs(0,[])

            def dfs2(n,a):
                if n==k:
                    val=0
                    res=1
                    for i in range(len(a)):
                        val+=a[i]*(10**(d-1-l-i)-10**(i+l))
                        if i!=0:
                            res*=10-abs(a[i])
                        else:
                            res*=10-abs(a[i])
                    if val not in dic2:
                        dic2[val]=0
                    dic2[val]+=res
                    return 0

                for i in range(-9,10):
                    dfs2(n+1,a+[i])

            dfs2(l,[])
            for i in dic1:
                if D-i in dic2:
                    ans+=dic1[i]*dic2[D-i]

        else:
            k=d//2
            l=k//2
            def dfs(n,a):
                if n==l:
                    val=0
                    res=1
                    for i in range(len(a)):
                        val+=a[i]*(10**(d-1-i)-10**i)
                        if i!=0:
                            res*=10-abs(a[i])
                        else:
                            res*=9-abs(a[i])
                    if val not in dic1:
                        dic1[val]=0
                    dic1[val]+=res
                    return 0

                for i in range(-9,10):
                    dfs(n+1,a+[i])

            dfs(0,[])

            def dfs2(n,a):
                if n==k:
                    val=0
                    res=1
                    for i in range(len(a)):
                        val+=a[i]*(10**(d-1-l-i)-10**(i+l))
                        if i!=0:
                            res*=10-abs(a[i])
                        else:
                            res*=10-abs(a[i])
                    if val not in dic2:
                        dic2[val]=0
                    dic2[val]+=res
                    return 0

                for i in range(-9,10):
                    dfs2(n+1,a+[i])

            dfs2(l,[])

            for i in dic1:
                if D-i in dic2:
                    ans+=dic1[i]*dic2[D-i]*10

    print(ans)
else:
    ans=0
    for d in range(1,18):
        dic1={}
        dic2={}
        if d%2==0:
            k=d//2
            l=k//2
            def dfs(n,a):
                if n==l:
                    val=0
                    res=1
                    for i in range(len(a)):
                        val+=a[i]*(10**(d-1-i)-10**i)
                        if i!=0:
                            res*=10-abs(a[i])
                        else:
                            res*=10-abs(a[i])
                    if val not in dic1:
                        dic1[val]=0
                    dic1[val]+=res
                    return 0

                for i in range(-9,10):
                    dfs(n+1,a+[i])

            dfs(0,[])

            def dfs2(n,a):
                if n==k:
                    val=0
                    res=1
                    for i in range(len(a)):
                        val+=a[i]*(10**(d-1-l-i)-10**(i+l))
                        if i!=0:
                            res*=10-abs(a[i])
                        else:
                            res*=10-abs(a[i])
                    if val not in dic2:
                        dic2[val]=0
                    dic2[val]+=res
                    return 0

                for i in range(-9,10):
                    dfs2(n+1,a+[i])

            dfs2(l,[])
            for i in dic1:
                if D-i in dic2:
                    ans+=dic1[i]*dic2[D-i]

        else:
            k=d//2
            l=k//2
            def dfs(n,a):
                if n==l:
                    val=0
                    res=1
                    for i in range(len(a)):
                        val+=a[i]*(10**(d-1-i)-10**i)
                        if i!=0:
                            res*=10-abs(a[i])
                        else:
                            res*=10-abs(a[i])
                    if val not in dic1:
                        dic1[val]=0
                    dic1[val]+=res
                    return 0

                for i in range(-9,10):
                    dfs(n+1,a+[i])

            dfs(0,[])

            def dfs2(n,a):
                if n==k:
                    val=0
                    res=1
                    for i in range(len(a)):
                        val+=a[i]*(10**(d-1-l-i)-10**(i+l))
                        if i!=0:
                            res*=10-abs(a[i])
                        else:
                            res*=10-abs(a[i])
                    if val not in dic2:
                        dic2[val]=0
                    dic2[val]+=res
                    return 0

                for i in range(-9,10):
                    dfs2(n+1,a+[i])

            dfs2(l,[])

            for i in dic1:
                if D-i in dic2:
                    ans+=dic1[i]*dic2[D-i]*10

    print(ans*9*10**(count-1))

Solution (Python):
import sys
input = sys.stdin.readline

D = int(input())

memo_F = [0] * 30
memo_T = [0] * 30

for x in range(10):
    for y in range(10):
        memo_T[y-x] += 1
        if x != 0:
            memo_F[y-x] += 1

def F(K,D,allow_leading_zero):
    if K == 0:
        return 1 if D == 0 else 0
    if K == 1:
        if D != 0:
            return 0
        if allow_leading_zero:
            return 10
        else:
            return 9
    x = 10**(K-1)-1
    d = (-D)%10
    
    ret = 0
    for use_x in [d,d-10]:
        if allow_leading_zero:
            coef = memo_T[use_x]
        else:
            coef = memo_F[use_x]
        if coef == 0:
            continue
        ret += coef * F(K-2,(D-x*use_x)//10,True)
    return ret

answer = sum(F(K,D,False) for K in range(1,20))
print(answer)

Solution (Python):
def f(d,x,y):n=int("9"*x+"0"*y);return d==0 if x<1 else sum(f(d-i*n,x-2,y+1)*(10-abs(i)-(y<1))for i in [d/n,d/n+1]if -10<i<10)
D=input();print sum(f(D,i,0)*(10-i%2*9)for i in range(1,21))

Solution (Python):
def f(d,x,y):n=int("9"*x+"0"*y);return d==0 if x<1 else sum(f(d-i*n,x-2,y+1)*(10-abs(i)-(y<1))for i in range(-9,10)if abs(d-i*n)<n)
D=input();print sum(f(D,i,0)*(10-i%2*9)for i in range(1,21))

Solution (Python):
def f(d,x,y):n=int("9"*x+"0"*y);return d==0 if x<1 else sum(f(d+i*n,x-2,y+1)*(10-abs(i)-(y<1))for i in range(-9,10)if abs(d+i*n)<n)
D=input();print sum(f(D,i,0)*(10-i%2*9)for i in range(1,21))

Solution (Python):
def func(d, x, y):
    n = int("9" * x + "0" * y)
    return d == 0 if x < 1 else sum(func(d + i * n, x - 2, y + 1) * (10 - abs(i) - (y < 1)) for i in range(-9, 10) if abs(d + i * n) < n)
D = input();print sum(func(D, i, 0) * (10 - i % 2 * 9) for i in range(1, 21))

Solution (Python):
def func(d, cnt9, cnt0):
    if cnt9 < 1 : return d == 0
    n = int("9" * cnt9 + "0" * cnt0)
    return sum(func(d + i * n, cnt9 - 2, cnt0 + 1) * (9 - abs(i) + 1 - (cnt0 < 1)) for i in range(-9, 10) if abs(d + i * n) < n)

D = input()
print sum(func(D, i, 0) * (10 - i % 2 * 9) for i in range(1, 21))

Solution (Python):
def func(diff, cnt9, cnt0):
    if cnt9 <= 0 : return diff == 0
    num = int("9" * cnt9 + "0" * cnt0)
    return sum(func(diff + i * num, cnt9 - 2, cnt0 + 1) * (9 - abs(i) + 1 - (cnt0 < 1)) for i in range(-9, 10) if abs(diff + i * num) < num)

D = input()
print sum(func(D, d, 0) * (10 - d % 2 * 9) for d in range(1, 21))

Solution (Python):
import itertools as ite
import math
import random

INF = 10 ** 18
MOD = 10 ** 9 + 7

def func(diff, cnt9, cnt0):
    if cnt9 <= 0:
        return (diff == 0)
    num = int("9" * cnt9 + "0" * cnt0)
    return sum(func(diff + i * num, cnt9 - 2, cnt0 + 1) * (9 - abs(i) + 1 - (cnt0 < 1)) for i in range(-9, 10) if abs(diff + i * num) < num)

D = input()

ans = 0
for d in range(1, 21):
    ans += func(D, d, 0) * (10 - d % 2 * 9)
print ans

Solution (Python):
import itertools as ite
import math
import random

INF = 10 ** 18
MOD = 10 ** 9 + 7

def func(diff, cnt9, cnt0):
    if cnt9 <= 0:
        return (diff == 0)
    num = int("9" * cnt9 + "0" * cnt0)
    return sum(func(diff + i * num, cnt9 - 2, cnt0 + 1) * (9 - abs(i) + 1 - (cnt0 < 1)) for i in range(-9, 10) if abs(diff + i * num) < num)

D = input()

ans = 0
for d in range(1, 21):
    MUL = 1 if d % 2 == 1 else 10
    ans += func(D, d, 0) * MUL
print ans

Solution (Python):
import itertools as ite
import math
import random

INF = 10 ** 18
MOD = 10 ** 9 + 7

def func(diff, cnt9, cnt0):
    if cnt9 <= 0:
        return (diff == 0)
    num = int("9" * cnt9 + "0" * cnt0)
    ret = 0
    for i in range(-9, 10):
        if abs(diff + i * num) < num:
            MUL = 9 - abs(i) + 1
            MUL -= (cnt0 == 0)
            ret += func(diff + i * num, cnt9 - 2, cnt0 + 1) * MUL
    return ret

D = input()

ans = 0
for d in range(1, 21):
    MUL = 1 if d % 2 == 1 else 10
    ans += func(D, d, 0) * MUL
print ans

Solution (Python):
from collections import deque
D=int(input())
def f(d,k):
  if 0<=k<=1:
    if d!=0:
      return "Unko"
    if k==1:
      return deque([0])
    else:
      return deque([])
  if d>=0:
    s=10-(d%10)
  else:
    s=-(d%10)
  if s==10:
    A=f(d//10,k-2)
    s=0
  
  else:
    A=f((d-s*(10**(k-1))+s)//10,k-2)
    
  if A=="Unko":
    return "Unko"
  A.appendleft(s)
  A.append(-s)

  return A
ans=0
for k in range(1,50):
  A=f(D,k)
  if A=="Unko":
    continue
 
  res=1
  for j in range((k+1)//2):
    if j==0:
      res*=9-abs(A[j])
    else:
      if A[j]==0:
        res*=10
      else:
        res*=10-abs(A[j])
  ans+=res
print(ans)

Solution (Python):
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, 20):
    if not l:
        ans += rec(D, i, i)
    else:
        ans += rec(D, i, 100)
print(a * ans)

Solution (Python):
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) <= A[pos]:
					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) <= A[pos]:
					curr += recurse(pos + 1, made + i * A[pos]) * ways_in_other[i]

			return curr

	res += bonus * recurse(0, 0)

print res

Solution (Python):
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+1):
  result += solve(D, k)

print(result)

Solution (Python):



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

  t = (-d)%10 
  d -= t*10**(k-1) - t
  return (10-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)

Solution (Python):
def result(letters, number, cant_zero):
    if letters <= 1:
        if number == 0:
            return 10 ** letters
        return 0
    diff = (10 - number%10) % 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)

Solution (Python):
def solve(k, d, fl):
    if k <= 1:
        if d == 0:
            return 10 ** k
        return 0
    x = (-d) % 10
    c = 9 - x + 1 - fl
    d -= 10 ** (k - 1) * x - x
    return c * solve(k - 2, abs(d) // 10, 0)

d = int(input())

ans = 0
for i in range(1, 100):
    ans += solve(i, d, 1)
print(ans)