問題
http://community.topcoder.com/stat?c=problem_statement&pm=10992&rd=14239
ある整数sからtに変換したい。
変換には＋、＊、ー、／の４つの操作があり、＋は現在の数と同じ数を足し、
＊は現在の数と同じ数をかけ、ーは現在の数と同じ数を引き、／は同じ数を割る。
このとき、ｔに変換したときの操作手順を返す。
複数の操作手順があるときは少ない手順数のものを、同じ手順数であれば
辞書順で最小のものを返す。
そのような手順がないときは”:-(”を返す。
解き方
まず、ーにしたときは０となり、答えは１以上であるためーは使用しない。
次に、＋と＊の操作をしたときは
操作後の数がtから割れる数にならなければならない。
このような数について、幅優先探索で調べていく。
また、／は数を１にして調べていくので、最初に／がある場合も
一緒に調べればよい。
コード
class OneRegister {
public: string getProgram(int s, int t) {
if(s==t)return "";
map<long long,string> m;
string ret="";
queue<pair<long long,string> > q;
q.push(make_pair(s,""));
q.push(make_pair(1,"/"));
while(!q.empty()){
long long x=q.front().first;
string str=q.front().second;
q.pop();
if(x==t){
if(ret.empty() || ret.size()>str.size() ||
(ret.size()==str.size() && ret>str))ret=str;
}
if(t%(x*2)==0){
q.push(make_pair(x*2,str+'+'));
}
if(x!=1 && t%(x*x)==0){
q.push(make_pair(x*x,str+'*'));
}
}
return !ret.empty() ? ret : ":-(";
}
};
public: string getProgram(int s, int t) {
if(s==t)return "";
map<long long,string> m;
string ret="";
queue<pair<long long,string> > q;
q.push(make_pair(s,""));
q.push(make_pair(1,"/"));
while(!q.empty()){
long long x=q.front().first;
string str=q.front().second;
q.pop();
if(x==t){
if(ret.empty() || ret.size()>str.size() ||
(ret.size()==str.size() && ret>str))ret=str;
}
if(t%(x*2)==0){
q.push(make_pair(x*2,str+'+'));
}
if(x!=1 && t%(x*x)==0){
q.push(make_pair(x*x,str+'*'));
}
}
return !ret.empty() ? ret : ":-(";
}
};