これSRMとかで出たらしんどそう。
http://codeforces.com/contest/991/problem/F
問題
整数Nが与えられる。
1000000007→10^9+7のように、加算・乗算・指数演算の記号のみ用いて、Nをより短い文字数で表記せよ。
ただしa^b^cのように指数演算記号を複数連ねることは不可。
解法
幸いサンプルでN=10^10は示してくれているので、N＜10^10の場合を考える。
とすると、演算記号を使う場合は9文字以下でなければならない。
以下の場合を列挙しよう。
+を1つも含まない場合
N=A*B^Cの形で表すことになる。
Cは2以上でなければならないので、B,Cを総当たりすればよい。
+を含む場合
文字列表記の文字数より多い桁を表すには指数表記を使うしかない。
よってその場合３文字は必須である。
また、全体で９文字以下なので、+を含むと必ず１つは４文字以下の項ができる。
さらに、４文字以下の指数表記ではA*B^Cの形はとれず、B^Cの形しか取れない。
よって、最初にB^Cの形で４文字以下で表記できる整数を列挙しておこう。
B,Cが高々２ケタなのでこれは容易である。
N=####+(4文字以下)のケース
- の右側に来る４ケタ以下の値(Mとする)を総当たりしよう。
左側は(N-M)について、上記+を含まないケースを探せばよい。
N=(4文字以下)+(4文字以下)のケース
N=(3文字)+(3文字)+(1文字)のケース
N=(3文字)*(3文字)+(1文字)のケース
4文字以下のケースは1000通りもないので、これらはそれぞれ総当たりする。
ll V;
unordered_map<ll,string> po;
string ret;
string no_plus(ll v) {
string ret=to_string(v);
// no plus
for(ll a=2;a*a<=v;a++) {
ll b=a*a;
int c=2;
while(v%b==0) {
string s;
if(v/b>1) s=to_string(v/b)+"*"+to_string(a)+"^"+to_string(c);
else s=to_string(a)+"^"+to_string(c);
if(s.size()<ret.size()) ret=s;
c++;
b*=a;
}
}
return ret;
}
void solve() {
int i,j,k,l,r,x,y; string s;
cin>>V;
if(V==10000000000LL) return _P("100^5\n");
ret=no_plus(V);
// 4*4
for(x=2;x<=99;x++) {
ll v=1;
for(y=1;y<=99;y++) {
v*=x;
if(v>V) break;
if(x>=10 && y>=10) break;
string tmp=to_string(x)+"^"+to_string(y);
if(po.count(v)==0 || po[v].size()>tmp.size()) po[v]=tmp;
}
}
for(i=0;i<1000;i++) po[i]=to_string(i);
// one plus
FORR(p,po) {
ll v=V-p.first;
if(v>0) {
string tmp=p.second+"+"+no_plus(v);
if(tmp.size()<ret.size()) ret=tmp;
}
}
// two plus
FORR(p,po) FORR(p2,po) {
ll v=V-p.first-p2.first;
if(po.count(v)) {
string tmp=p.second+"+"+p2.second;
if(v) tmp+="+"+po[v];
if(tmp.size()<ret.size()) ret=tmp;
}
v=V-p.first*p2.first;
if(po.count(v)) {
string tmp=p.second+"*"+p2.second;
if(v) tmp+="+"+po[v];
if(tmp.size()<ret.size()) ret=tmp;
}
}
cout<<ret<<endl;
}
まとめ
N=(3文字)*(3文字)+(1文字) のケースを見逃した。
