AOJ2424 Kakezan

問題文: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2424

解法

a+b桁の数Nのうち左a桁をA、右b桁をBとします。
その時、Nの次の数N2は
N = A*10^b+B >= A*10^b > A*B
より、必ずN>N2となります。
なので一桁の数になるまでシミュレーションを繰り返して解を求めます。

以下のコードで0:00 sec 1260 KBでAC。

#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<sstream>
#include<algorithm>
using namespace std;
int Solve(int n)
{
	if(n<10)
		return 0;
	stringstream ss;
	ss<<n;
	string s=ss.str();
	int t=0;
	for(int i=1;i<s.size();++i)
		t=max(t,atoi(s.substr(0,i).c_str())*atoi(s.substr(i).c_str()));
	return 1+Solve(t);
}
int main()
{
	int q,n;
	for(scanf("%d",&q);q--;)
	{
		scanf("%d",&n);
		printf("%d\n",Solve(n));
	}
	return 0;
}