# Problem B: Tight words

Problem B: Tight words

## 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 is tight if any two neighbour digits in the word do not differ by more than 1.

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

``````4 1
2 5
3 5
8 7
``````

``````100.00000
40.74074
17.38281
0.10130
``````

``````#include <stdio.h>

char *k = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";

main(){
int i,c;
while (EOF != (c = getchar())) {
for (i=1;k[i] && k[i]!=c;i++);
if (k[i]) putchar(k[i-1]); else putchar(c);
}
}``````

``````#include <stdio.h>

double x[100][10];  double s;

main(){
int i,j,k,n;
while (2 == scanf("%d%d",&k,&n)){
k++;
for (i=0;i<n;i++) for (j=0;j<k;j++) x[i][j] = 0;
for (i=0;i<k;i++) x[0][i] = 100.0/k;
for (i=1;i<n;i++) {
for (j=0;j<k;j++) x[i][j] += x[i-1][j]/k;
for (j=1;j<k;j++) x[i][j] += x[i-1][j-1]/k;
for (j=0;j<k-1;j++) x[i][j] += x[i-1][j+1]/k;
}
for (s=i=0;i<k;i++) s += x[n-1][i];
printf("%0.5lf\n",s);
}
}``````