Problem B: Tight words

Problem B: Tight words

时间： 1ms        内存：128M

描述：

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

提示：

参考答案（内存最优[748]）：

#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);
   }
}

参考答案（时间最优[0]）：

#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);
   }
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。