SRM 437 DIV1 Easy - TheSwap

SRM 437 DIV1 Easy - TheSwap

17:14

問題


http://community.topcoder.com/stat?c=problem_statement&pm=10369&rd=13699

解き方


全探索可能な問題。
setとvectorを利用して、各繰り返し回数で生成される数を更新していく。

コード


class TheSwap {

public: int findMax(int n, int k) {
set<int> cur,next;
cur.insert(n);

FORE(i,0,k){
for(set<int>::iterator it=cur.begin();it!=cur.end();it++){
int x=*it;
vector<int> vx;
while(x>0){
vx.push_back(x%10);
x/=10;
}

FORE(a,0,vx.size())FORE(b,a+1,vx.size()){
if(!(b==vx.size()-1 && vx[a]==0)){
swap(vx[a],vx[b]);
int tmp=0;
for(int c=vx.size()-1;c>=0;c--)tmp=tmp*10+vx[c];
next.insert(tmp);
swap(vx[a],vx[b]);
}
}
}
cur=next;
next.clear();
}

int ret=0;
if(cur.empty())return -1;
for(set<int>::iterator it=cur.begin();it!=cur.end();it++){
ret=max(ret,*it);
}

return ret;
}

};

Share this

Google Facebook Twitter More

Related Posts