AOJ2044 Lying about Your Age

AOJ Volume20

問題リンク Lying about Your Age

  • 概要

新しい街に引っ越してきて、あなたは自分の年齢を他人に知られたくない。自分の真の年齢をM進数表現(2 <= M <= 16)したものを、10進数表現とみなしたものを自分の年齢として主張する。1年ごとに自分の年齢の主張を変える必要がある。主張する年齢には0〜9の数字のみが含まれている必要があり、更に去年に主張した年齢と同じかそれより大きい年齢を主張しなければならない。
入力に3つの整数A, B, Cが与えられる。真の年齢がAのときにBと主張したとする。このとき、真の年齢がCとなったときに主張することができる年齢の最小値を答えよ。また、AをBと主張できない場合は-1と答えよ。
0 <= A < C <= 200
Bは8ケタ以下の整数

  • 解法

貪欲法で解きます。
前年の主張年齢をb、今年の真の年齢がXのとき、XをM進数表記した結果のうちで、b以上のもののうち最小値を今年の主張年齢とすればいいと分かります。
XをM進数表記したときにa〜fの表記がでてしまうものは主張することができないことに気をつけましょう。

  • ソース
import java.util.Scanner;

//Lying about Your Age
public class AOJ2044 {

	int INF = 1<<29;
	
	int f(int x, int b){
		String res = "";
		while(x>0){
			int r = x%b;
			if(10<=r)return INF;
			res = r+res;
			x/=b;
		}
		return Integer.parseInt(res);
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int[][] a = new int[201][17];
		for(int i=1;i<=200;i++)for(int j=2;j<=16;j++)a[i][j]=f(i, j);
		for(;;){
			int A = sc.nextInt(), B = sc.nextInt(), C = sc.nextInt();
			if(A<0)break;
			int res = INF;
			for(int j=2;j<=16;j++)if(a[A][j]==B)res=B;
			for(int i=A+1;i<=C;i++){
				int next = INF;
				for(int j=2;j<=16;j++)if(res<=a[i][j])next = Math.min(next, a[i][j]);
				res = next;
			}
			System.out.println(res==INF?-1:res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2044().run();
	}
}