2013
11-11

# 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


//* @author:
import java.util.*;
public class Main {

static public void main( String [] str ){
Scanner sc = new Scanner(System.in);
while( sc.hasNext())
{
int k=sc.nextInt();
int n=sc.nextInt();
double ans[][]=new double[n][k+1];
for( int i=0; i< n; i++ )
s *= (k+1);

for(int  j=0; j<=k; j++ )
ans[0][j] = 1/s;

for(int  i=1; i< n; i++ )
for(int j=0; j<=k; j++ )
{
ans[i][j] = ans[i-1][j];
if( j!=0) ans[i][j] += ans[i-1][j-1];
if( j< k ) ans[i][j] += ans[i-1][j+1];
}

for( int j=0; j<=k; j++ )
}

}
}

1. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测

2. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;