Problem p03704 (python)

Fixed submission:
# (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 # 10-d%10 doesn't work when 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)

Buggy submission (verdict: Runtime Error):


# (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(D.copy())

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

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

print(r)

Buggy submission (verdict: Runtime Error):


# (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

  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 = str(r)+'0'*(leading_zeros-1)

  return r


from collections import deque


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

print(solve(D))

Buggy submission (verdict: Runtime Error):


# (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

  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) > 1:
    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) == 1:
    r *= 10 if D[0] == 0 else 0

  if r != 0 and leading_zeros > 0:
    r *= 9
    r = str(r)+'0'*(leading_zeros-1)

  return r


from collections import deque

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

Buggy submission (verdict: Runtime Error):
from collections import deque

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

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

# (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):
  r = 1
  while len(D) > 1:
    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) == 1:
    r *= 10 if D[0] == 0 else 0
  return r

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

r *= solve(D)

if leading_zeros > 0:
  r *= 9
  r = str(r)+'0'*(leading_zeros-1)

print(r)

Buggy submission (verdict: Runtime Error):
from collections import deque

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

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

# (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):
  r = 1
  while len(D) > 1:
    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 = -1
      while D[i] == 10:
        D[i] = 0
        D[i-1] += 1
        i -= 1
    else:
      r = 0
      D.clear()

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

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 = -1
    while D[i] == 10:
      D[i] = 0
      D[i-1] += 1
      i -= 1

r *= solve(D)

if leading_zeros > 0:
  r *= 9
  r = str(r)+'0'*(leading_zeros-1)

print(r)

Buggy submission (verdict: Runtime Error):

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)
    t -= 10
    if -1 <= t <= 0:
      sub[-1] += t*10
      sub[0] += 1
      return (tail-outer)*rec(sub)


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)

Buggy submission (verdict: Runtime Error):

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)
    t -= 10
    if -1 <= t <= 0:
      sub[-1] += t*10
      sub[0] += 1
      return (tail-outer)*rec(sub)


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

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

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