代碼
import sys
import functools
@functools.lru_cache()
def get_ladder_number_count_for_length(length):
ans = 0
for j in range(9):
ans += matrix[length][j]
return ans
def make_triangle(length):
matrix = [[0]*9 for _ in range(length)]
for i in range(9):
matrix[0][i] = 1
for i in range(length):
matrix[i][0] = 1
for i in range(1,9):
for j in range(1,length):
matrix[j][i] = matrix[j-1][i] + matrix[j][i-1]
return matrix
def read_input():
numbers = []
max_length = 0
while True:
num = sys.stdin.readline().strip()
if not num:
break
numbers.append(num)
if len(num) > max_length:
max_length = len(num)
return numbers, max_length
def answer(numbers, matrix):
for number in numbers:
ans = 0
length = len(number)
length_minus_one = length-1
for i in range(length_minus_one):
ans += get_ladder_number_count_for_length(i)
for sequence, digit in enumerate(number):
forming_ladder_on_left = True
if sequence != 0:
if int(number[sequence-1]) > int(number[sequence]):
forming_ladder_on_left = False
if forming_ladder_on_left is True:
left_ind = sequence-1
if left_ind < 0:
left_num = 1
else:
left_num = int(number[left_ind])
for i in range(left_num, int(digit)):
ans += matrix[length-1-sequence][-i]
else:
break
if forming_ladder_on_left:
ans+=1
print(str(ans))
numbers, max_length = read_input()
matrix = make_triangle(max_length)
answer(numbers, matrix)