当前位置:首页 » Project Euler » 详细页

Step Numbers 题号:178 难度: 55 中英对照

Consider the number 45656.
It can be seen that each pair of consecutive digits of 45656 has a difference of one.
A number for which every pair of consecutive digits has a difference of one is called a step number.
A pandigital number contains every decimal digit from 0 to 9 at least once.
How many pandigital step numbers less than 1040 are there?

Solution

按数位动态规划。 设$dp[i][x][y][a]$表示第$i$位填数字$a$,且前$i$位是否包含$0$($x$)、是否包含$9$($y$),其中$0\leq i < 40,\quad 0\leq x,y \leq 1, \quad 0\leq a \leq 9$。 递推式由$dp[i][x][y][a]$向$dp[i+1][x][y][a\pm 1]$贡献答案,详见代码即可。

Code

import java.util.Arrays;

public final class p178 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }

	
    static public String run() {
    	final int Limit=40;
		long[][][][] a = new long[Limit][2][2][10];
		Arrays.fill(a[0][0][0], 1);
		Arrays.fill(a[0][0][1], 0);
		Arrays.fill(a[0][1][0], 0);
		Arrays.fill(a[0][1][1], 0);
		a[0][0][0][0] = 0;
		a[0][0][0][9] = 0;
		a[0][0][1][9] = 1;

		for (int n = 1; n < Limit; n++) {
			for (int digit = 0; digit < 10; digit++) {
				if (digit == 0) {
					a[n][1][0][digit + 1] += a[n - 1][1][0][digit];
					a[n][1][1][digit + 1] += a[n - 1][1][1][digit];
				} else if (digit == 1) {
					a[n][1][0][digit - 1] += a[n - 1][0][0][digit];
					a[n][0][0][digit + 1] += a[n - 1][0][0][digit];
					a[n][1][1][digit - 1] += a[n - 1][0][1][digit];
					a[n][0][1][digit + 1] += a[n - 1][0][1][digit];
					a[n][1][0][digit - 1] += a[n - 1][1][0][digit];
					a[n][1][0][digit + 1] += a[n - 1][1][0][digit];
					a[n][1][1][digit - 1] += a[n - 1][1][1][digit];
					a[n][1][1][digit + 1] += a[n - 1][1][1][digit];
				} else if (digit == 8) {
					a[n][0][0][digit - 1] += a[n - 1][0][0][digit];
					a[n][0][1][digit + 1] += a[n - 1][0][0][digit];
					a[n][1][0][digit - 1] += a[n - 1][1][0][digit];
					a[n][1][1][digit + 1] += a[n - 1][1][0][digit];
					a[n][0][1][digit - 1] += a[n - 1][0][1][digit];
					a[n][0][1][digit + 1] += a[n - 1][0][1][digit];
					a[n][1][1][digit - 1] += a[n - 1][1][1][digit];
					a[n][1][1][digit + 1] += a[n - 1][1][1][digit];
				} else if (digit == 9) {
					a[n][0][1][digit - 1] += a[n - 1][0][1][digit];
					a[n][1][1][digit - 1] += a[n - 1][1][1][digit];
				} else {
					a[n][0][0][digit - 1] += a[n - 1][0][0][digit];
					a[n][0][0][digit + 1] += a[n - 1][0][0][digit];
					a[n][0][1][digit - 1] += a[n - 1][0][1][digit];
					a[n][0][1][digit + 1] += a[n - 1][0][1][digit];
					a[n][1][0][digit - 1] += a[n - 1][1][0][digit];
					a[n][1][0][digit + 1] += a[n - 1][1][0][digit];
					a[n][1][1][digit - 1] += a[n - 1][1][1][digit];
					a[n][1][1][digit + 1] += a[n - 1][1][1][digit];
				}
			}
		}

		long result = 0;
		for (int n = 0; n < Limit; n++) {
			for (int digit = 0; digit < 10; digit++) {
				result = result + a[n][1][1][digit];
			}
		}
    	return ""+result;
    }
}
126461847755
0ms