分饼干

[编程题]分饼干

热度指数：2194 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字k有些数位变得模糊了，看不清楚数字具体是多少了。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证这盒饼干能平分给n个小朋友。现在你需要计算出k有多少种可能的数值

输入描述:

输入包括两行：
 第一行为盒子上的数值k，模糊的数位用X表示，长度小于18(可能有多个模糊的数位)
 第二行为小朋友的人数n

输出描述:

输出k可能的数值种数，保证至少为1

示例1

输入

9999999999999X 3

输出

算法知识视频讲解

Python

周昆

上一个python版本的动态规划。

# -*- coding: utf-8 -*-
# 输入k,n
k = raw_input() 
n = int(raw_input())
remainders = [1] + [0] * (n - 1)

for i, s in enumerate(k):
	temp = [0] * n
	if s != 'X':
		s = int(s)
		for j in range(n):
			temp[(j*10+s) % n] += remainders[j]
	else:
		for s in range(10):
			for j in range(n):
				temp[(j*10+s) % n] += remainders[j]
	remainders = temp
print remainders[0]

发表于 2017-04-14 11:27:20 回复(1)