Таки LLM много че изменили, в другое время пришлось бы сидеть и думать, а щас, за 1 минуту тебе выдается результат, да возможно не самый оптимальный/красивый, но все же...
def count_numbers_with_digit_sum(limit, target_sum):
limit_digits = [int(d) for d in str(limit)]
memo = {}
def dp(pos, sum_so_far, tight, isStart):
if sum_so_far > target_sum:
return 0
if pos == len(limit_digits):
return int(isStart and sum_so_far == target_sum)
key = (pos, sum_so_far, tight, isStart)
if key in memo:
return memo[key]
total = 0
max_digit = limit_digits[pos] if tight else 9
for digit in range(0, max_digit + 1):
new_tight = tight and (digit == limit_digits[pos])
new_isStart = isStart or digit != 0
if not new_isStart:
# Leading zeros, don't add to sum
total += dp(pos + 1, sum_so_far, new_tight, new_isStart)
else:
total += dp(pos + 1, sum_so_far + digit, new_tight, new_isStart)
memo[key] = total
return total
return dp(0, 0, True, False)
def main():
limit = 2 ** 63
target_sum = 159
result = count_numbers_with_digit_sum(limit, target_sum)
print(result)
if __name__ == "__main__":
main()
.png.8366142ab64f0a33d537443cf80608cc.png)
.thumb.png.72e07cb11b543dd693dce85f3230f4e8.png)
