Tight words

http://acm.pku.edu.cn/JudgeOnline/problem?id=2537

Description

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

Input is a sequence of lines, each line contains two integer numbers k and n, 1 <= n <= 100.

Output

For each line of input, output the percentage of tight words of length n over the alphabet {0, 1, ... , k} with 5 fractional digits.

Sample Input

4 1
2 5
3 5
8 7

Sample Output

100.00000
40.74074
17.38281
0.10130

Source

Waterloo local 2001.01.27


Solving

알파벳 {0, 1, 2, ..., k | 0 <= k < = 9} 으로 만들 수 있는 n자리의 숫자 중 인접한 두 자리의 숫자의 차이가 1이하인 숫자가 나타날 확률을 구하라

i번째 자리에 숫자j가 나타났을 때 문제의 조건을 만족할 확률을 D[j][i]라고 정의하자

첫번째 자리에 0 부터 k까지의 숫자가 나타나는 경우 문제의 조건을 만족한다.(한 자리 수 이므로)
따라서, D[0...k][1] = 1/(k+1)이다.

두번째 자리에 0이 나타나면서 문제의 조건을 만족하려면 첫번째 자리가 0이거나 1이어야 한다.
따라서, D[0][1] = (D[0][0] + D[1][0]) * (1/(k+1)) 이다.
두번째 자리에 1이 나타나면서 문제의 조건을 만족하려면 첫번째 자리가 0, 1, 2 중 하나여야 한다.
따라서, D[1][1] = (D[0][0] + D[1][0] + D[2][0]) * (1/(k+1)) 이다.
..
두번째 자리에 k가 나타나면서 문제의 조건을 만족하려면 첫번째 자리가 k-1, k 중 하나여야 한다.
따라서, D[1][k] = (D[0][k-1] + D[0][k]) * (1/(k+1)) 이다.

일반화를 해보면,
i번째 자리에 j가 나타나면서 문제의 조건을 만족하려면 i-1번째 자리가 {j-1, j, j} 중 하나여야 한다.
따라서 점화식은,

D[j][i] = (D[j-1][i-1] + D[j-1][i] + D[j+1][i]) * (1/(k+1))

이다.

예외가 되는 j가 0일 때와 k일 때만 조심해서 구현하면 된다.

#include <cstdlib> #include <cstdio> int main() { int k, n; while (scanf("%d%d", &k, &n) > 0) { if (k <= 1) { printf("100.00000\n"); continue; } int i, j; double d[10][101] = {0}; double kp = (1.0/(k+1)); for (i = 0; i <= k; i++) d[i][1] = kp; for (i = 1; i < n; i++) { d[0][i+1] += d[0][i] * kp; d[1][i+1] += d[0][i] * kp; d[k][i+1] += d[k][i] * kp; d[k-1][i+1] += d[k][i] * kp; for (j = 1; j <= k-1; j++) { d[j][i+1] += d[j][i] * kp; d[j-1][i+1] += d[j][i] * kp; d[j+1][i+1] += d[j][i] * kp; } } double p = 0; for (i = 0; i <= k; i++) p += d[i][n]; printf("%.5lf\n", p*100); } return 0; }