其实有很多这样的活动都有一个相同的模式:N 种人物卡片,每次买一包干脆面随机得到一张。当你集齐这 N 种人物时,就会有相应的奖励。 那时候还不懂怎么计算概率,白白给人家送了好多钱,吃了好多干脆面。 现在的任务是,给你一个正整数 N (1 <= N <= 10^4),请你帮我从期望的角度计算平均需要买多少包干脆面才能集齐这 N 种人物。 提醒:由于结果可能不是整数,所以结果只保留到小数点后两位。
概率DP 假设手中现在有x张卡片,那么再买一包得到新卡片的概率为
\frac {N-x}{N}
则期望步数为
\frac {N}{N-x}
def solve(n):
r = 0.0
for i in range(0, n):
r += (1.0 * n) / (n - i)
return r
print '%.2f' % solve(N)
银行在打印票据的时候,常常需要将阿拉伯数字表示的人民币金额转换为大写表示,现在请你来完成这样一个程序。 在中文大写方式中,0到10以及100、1000、10000被依次表示为: 零壹贰叁肆伍陆柒捌玖拾佰仟万 以下的例子示范了阿拉伯数字到人民币大写的转换规则: 1 壹圆 11 壹拾壹圆 111 壹佰壹拾壹圆 101 壹佰零壹圆 -1000 负壹仟圆 1234567 壹佰贰拾叁万肆仟伍佰陆拾柒圆 现在给你一个整数a(|a|<100000000), 打印出人民币大写表示. 注意:请以Unicode的形式输出答案。你可以通过decode("utf8")来将utf8格式的字符串解码为Unicode,例如你要输出ans = "零圆", print ans.decode("utf8"). Note:数据已于2013-11-19日加强,原来通过的代码可能不能再次通过。
#coding = 'utf-8'
def f(a):
W = ['万','拾','佰','仟']
L = ['零','壹','贰','叁','肆','伍','陆','柒','捌','玖']
flag = ''
if a < 0:
flag = '负'
a = -a
i = 0
ans = '圆'
nonzero = False
if a == 0:
ans += L[0]
while a > 0:
if a % 10 == 0:
if nonzero:
nonzero = False
ans += L[0]
else:
if i > 0:
ans += W[i % 4]
ans += L[a % 10]
nonzero = True
i += 1
a /= 10
return flag.decode('utf8') + ans.decode('utf8')[::-1]
print f(a)
给你一个字符串a和一个正整数n,判断a中是否存在长度为n的回文子串。如果存在,则输出YES,否则输出NO。 回文串的定义:记串str逆序之后的字符串是str1,若str=str1,则称str是回文串,如"abcba".
def manacher(s, n): r = '#' for c in s: r += c + '#' p = 0 mx = 0 a = [1] for i in range(1, len(r) - 1): a.append(0) if mx > i: a[i] = min(a[2 * p - i], mx - i) else: a[i] = 1 while (i >= a[i]) and (i + a[i] < len(r)) and (r[i - a[i]] == r[i + a[i]]): a[i] += 1 if a[i] - (i & 1) >= n: return True if i + a[i] > mx: p = i mx = i + a[i] return False if manacher(a, n): print 'YES' else: print 'NO'