読者です 読者をやめる 読者になる 読者になる

hogloidのブログ

へなちょこ

PKU 2611 Gas Station Numbers

http://poj.org/problem?id=2611
今ある数字の札を使った次に大きい価格を求めます。
2<ー>5、9<ー>6 は変換可能

まぁやるだけ
下の桁からみていって、今の桁の数より大きい数に変更できるなら、
その数に変更 後は残った数を小さくなるように置いていく

int main(){
	string s;
	while(cin>>s){
		if(s==".") break;
		reverse(ALL(s));
		string res=s;
		vi bef(10);
		REP(i,s.size()){
			if(s[i]=='.') continue;
			++bef[s[i]-'0'];
			if(s[i]=='6') ++bef[9];
			if(s[i]=='2') ++bef[5];
			if(s[i]=='5') ++bef[2];
			if(s[i]=='9') ++bef[6];

			REPN(j,10,s[i]-'0'+1){
				if(bef[j]){
					res[i]=j+'0';
					--bef[j];
					if(j==9) --bef[6];
					if(j==5) --bef[2];
					for(int k=i-1;k>=0;--k){
						if(res[k]=='.') continue;
						for(int l=0;l<=8;++l){
							if(l==5 || bef[l]==0) continue;
							res[k]=l+'0';
							--bef[l];
							break;
						}
					}
					goto exi;
				}
			}
		}
		exi:;
		if(res==s) puts("The price cannot be raised.");
		else{
			reverse(ALL(res));
			 cout<<res<<'\n';
		}
	}
	return 0;
}