Under construction

Still being built. Things may change

Tight Words

Interview

Time limit1sMemory limit128 MB

Summary
Count words of length n over digits 0..k where adjacent digits differ by at most 1, then print that count as a percentage rounded to five decimals.
Level

Medium5 of 10

Topics
Dynamic programming, Combinatorics, Math, Implementation
Solved
No attempts yet

Problem

Consider the alphabet {0,1,…,k}\{0, 1, \ldots, k\} where 0≤k≤90 \le k \le 9. A word of length nn over this alphabet is called tight if every pair of neighbouring digits differs by at most 11.

Input

The input consists of several lines. Each line contains two integers kk and nn (0≤k≤90 \le k \le 9, 1≤n≤1001 \le n \le 100). Process each line in order until the end of input (EOF).

Output

For each input line, print the percentage of tight words of length nn over the alphabet {0,1,…,k}\{0, 1, \ldots, k\}. That is, the number of tight words divided by the total number of words (k+1)n(k+1)^n, multiplied by 100100. Print the value rounded to exactly 55 fractional digits (ties, i.e. 0.50.5, round up).

Examples2

  1. Example 1

    Input
    4 1
2 5
3 5
8 7
    Expected output
    100.00000
40.74074
17.38281
0.10130

  2. Example 2

    Input
    9 2
    Expected output
    28.00000