1790:Base Numbers

keyword

動的計画法　Java

概要

数字列が与えられる。それを(a_0-a_1-...-a_n)_dの様に表す方法は何通りあるか求める問題。a_i

import java.util.*;
import java.math.*;

class Main {

	private static String base, last;
	private static int len;

	private static boolean isLess(int begin, int end){
		int l = end - begin;
		if((last.charAt(begin)=='0') && (l > 1)) return false;
		if(l != len) return l<len;
		for(int i=begin; i<end; i++)
			if(base.charAt(i-begin) != last.charAt(i))
				return last.charAt(i) < base.charAt(i-begin);
		return false;
	}

	private static BigInteger solve(String str){
		if(str.length()==1 && str.charAt(0)=='0') return BigInteger.ZERO;
		BigInteger ret = BigInteger.ZERO;
		for(int i=1; i<str.length(); i++){
			if(str.charAt(i) != '0'){
				base = str.substring(i);
				len = base.length();
				ret = ret.add(func(str.substring(0,i)));
			}
		}
		return ret;
	}
	
	private static BigInteger func(String str){
		if(str.equals("0")) return BigInteger.ONE;
		if(str.charAt(0) == '0') return BigInteger.ZERO	;
		BigInteger dp[] = new BigInteger[36];
		for(int i=0; i<36; i++) dp[i] = BigInteger.ZERO;
		last = str;
		int n = str.length();
		for(int i=0; i<n; i++){
			for(int j=0; j<=i; j++){
				if( isLess(j,i+1) ){
					dp[i] = dp[i].add((j==0)?BigInteger.ONE:dp[j-1]);
				}
			}
		}
		return dp[n-1];
	}

	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		for(;;){
			String line = in.nextLine();
			if(line.equals("#")) return ;
			BigInteger ans = solve(line);
			if(!ans.equals(BigInteger.ZERO)){
				System.out.printf("The code %s can represent %d numbers.\n", line, ans);
			}
			else{
				System.out.printf("The code %s is invalid.\n", line);
			}
		}
	}
}