2424-Kakezan

問題（外部リンク）

Kakezan | Aizu Online Judge

実装の概要

任意の桁で区切りを入れて計算する処理は記述を簡単にするためにあえて文字列のまま処理をしてみました。実行時間に不安はありましたが無事に制限時間内に実行が終了しました。
今回の問題では「有限回で終わらないなら」という条件があるためその判断方法で悩むところですが、結論から言えば必ず有限回で終わります。例えば、12345を12, 345と区切ったとしても明らかに積は12*1000よりも小さくなります。2桁以上のどの整数をどこで区切っても同じことが言えるのでこの操作の結果は単調減少となります。
なお、下記のコードでもACにはなりますが、テストケースには同じ数字ばかり計算させるようなものも含まれているためメモ化などの工夫によりより高速化が可能だと思います。

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int q = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < q; i++){
			String input = br.readLine();
			System.out.println(solve(input));
		}
	}
	
	static int solve(String str){
		int times = 0;
		while(true){
			int len = str.length();
			
			//1桁ならそのまま返す
			if(len == 1){
				return times;
			}
			
			//区切りの場所を変えつつ最大値を探す
			int max = 0;
			for(int i = 1; i < len; i++){
				int a = Integer.parseInt(str.substring(0, i));
				int b = Integer.parseInt(str.substring(i, len));
				
				if(max < a*b){
					max = a*b;
				}
			}
			
			str = Integer.toString(max);
			times++;
		}
	}

}