算法题：UVA 10081 - Tight Words （数论 dp）

算法题：UVA 10081 - Tight Words （数论 dp）2014-04-20 csdn accelerator_Problem B: Tight words

Given is an alphabet {0, 1, ... , k}, 0 <= k <= 9 .We say that a word of length n over this alphabet istight if any two neighbour digits in the word do not differby more than 1.

Input is a sequence of lines, each line contains two integer numbersk and n, 1 <= n <= 100. For eachline of input, output the percentage of tight words of lengthn over the alphabet {0, 1, ... , k} with 5 fractional digits.

Sample input

4 1

2 5

3 5

8 7

Output for the sample input

100.00000

40.74074

17.38281

0.10130