AOJ-ICPC 「かけざん」
問題
Kakezan | Aizu Online Judge
解説
値は文字列で管理するのが良いですね。
文字列長より1少ない数だけforを回して、文字列をstring::substr(開始位置, 何文字切り抜くか)で分割の仕方を全探索し、結果が最大になったものを次に持ち越す感じです。
文字列から数字への変換は、std::stoiやstd::stolなどが標準で用意されていますが、たまに謎のエラーに見舞われるので、自作したSTOLを使っています。
無理なら-1の判定を結構雑に書いたんですが、まあ通ったので良しとします。
#include <bits/stdc++.h> #define rep(i,j,k) for(int i=(int)j;i<(int)k;i++) #define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++) #define Sort(x) sort((x).begin(),(x).end()) #define all(x) (x).begin(),(x).end() #define fi first #define se second #define vi vector<int> #define INF (int)1e9 #define INFL 1e18 #define MOD 1000000007 #define pb push_back #define MP make_pair #define PI 3.1415926535 typedef long long int ll; typedef std::pair<int,int> P; int D=1; int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0}; using namespace std; ll STOL(string s){ ll ret=0; rep(i,0,s.size()){ ret+=(s[s.size()-i-1]-'0')*pow(10,i); } return ret; } int main(){ int n; cin>>n; rep(i,0,n){ int ans=0; int x; cin>>x; while(1){ string s=to_string(x); if(s.size()==1){ //1文字になれば終了 cout<<ans<<endl; break; } ll max_num=0; rep(i,1,s.size()){ //文字列の分割方法を全探索し、最大値を探します。 max_num=max(max_num,STOL(s.substr(0,i))*STOL(s.substr(i,s.size()-i))); } //最大値を次のループに持ち越します x=max_num; ans++; //1000000回操作しても1文字にならなければまあ無理そうなのでその時点で切ります。これで通ったので良いのです()。 if(ans==1000000){ cout<<-1<<endl; break; } } } return 0; }