
ZOJ Problem Set  1883
Given is an alphabet {0, 1, ... , k}, 0 <= k <= 9 . We say that a word of length n over this alphabet is tight if any two neighbour digits in the word do not differ by more than 1.
For each line of input, output the percentage of tight words of length n over the alphabet {0, 1, ... , k} with 5 fractional digits.
Source: University of Waterloo Local Contest 2001.01.27 