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

Hexadecimal numbers 题号:162 难度: 45 中英对照

In the hexadecimal number system numbers are represented using 16 different digits:

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

Solution

数位动态规划。 用solve函数表示其过程: solve(statu,bool,n)表示当前剩余n位未填,statu是一个二进制表示3个布尔状态,即0、1、A是否已经填入。 因为要考虑0的填入问题,所以填入0时,如果把状态置为0已填入,则需要该0不是前导零(因为前导零不算使用了0),所以solve需要多输入一个参数bool表示当前是否允许前导零。

Code


public final class p162 {
    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" );
    }

	private static final int _NIL = 0;
	private static final int _0 = 1;
	private static final int _1 = 2;
	private static final int _A = 4;
	private static final long p[] = new long[15];
	
    static public String run() {
		p[0] = 16L;
		for (int k = 1; k < p.length; k++)
			p[k] = 16 * p[k - 1];
		long ans=solve(_NIL, false, 16);
		return Long.toHexString(ans).toUpperCase();
    }

	private static long solve(int flags, boolean allowLeadingZero, int n) {
		if (n == 0) {
			if (flags == _0 + _1 + _A) {
				return 1;
			}
			return 0;
		}
		int k = n - 1;
		switch (flags) {
		case _NIL:
			return (13 * solve(_NIL, true, k))
					+ solve(allowLeadingZero ? _0 : _NIL, allowLeadingZero, k)
					+ solve(_1, true, k) + solve(_A, true, k);
		case _0:
			return (14 * solve(_0, true, k)) + solve(_0 + _1, true, k)
					+ solve(_0 + _A, true, k);
		case _1:
			return (14 * solve(_1, true, k)) + solve(_1 + _0, true, k)
					+ solve(_1 + _A, true, k);
		case _0 + _1:
			return (15 * solve(_0 + _1, true, k))
					+ solve(_0 + _1 + _A, true, k);
		case _A:
			return (14 * solve(_A, true, k)) + solve(_A + _0, true, k)
					+ solve(_A + _1, true, k);
		case _0 + _A:
			return (15 * solve(_0 + _A, true, k))
					+ solve(_0 + _1 + _A, true, k);
		case _1 + _A:
			return (15 * solve(_1 + _A, true, k))
					+ solve(_0 + _1 + _A, true, k);
		case _0 + _1 + _A:
			return p[k];
		}
		return 0L;
	}
}
3D58725572C62302
0ms