SRM 281 DIV1 Easy - IntegerGenerator (復習○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=6093&rd=9824
有効な一ケタの数字一覧と、現在の数字が与えられる。
現在の数字より大きく、かつ有効な数字のみで構成された数を求める。
ただし無効である場合は”INVALID INPUT”を返す。
解き方
例外判定がまずは大事。
現在の数字に無効な数字が含まれているか、０から始まるのであれば無効。
あとは一ケタ目から有効な数字をインクリメントしてあげればよい。
その桁において、元の数より大きい数になればそこで終了、
そうでなければ桁上がりするので次の桁に進む。
最後までインクリメントされるのであれば、最初に一番小さい有効な数字を足す。
コード
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class IntegerGenerator {
public: string nextInteger(vector<int> allowed, string current) {
int num[10]={0};
FORE(i,0,allowed.size())num[allowed[i]]=1;
FORE(i,0,current.size())if(num[current[i]-'0']==0)return "INVALID INPUT";
if(current[0]=='0')return "INVALID INPUT";
for(int i=current.size()-1;i>=0;i--){
int cur=current[i]-'0';
for(int j=cur+1;;j++){
if(num[j%10]){
current[i]=(j%10)+'0';
if(j%10>cur)return current;
break;
}
}
}
char ch;
FORE(i,1,10)if(num[i]){
ch=i+'0';
break;
}
return ch+current;
}
};
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class IntegerGenerator {
public: string nextInteger(vector<int> allowed, string current) {
int num[10]={0};
FORE(i,0,allowed.size())num[allowed[i]]=1;
FORE(i,0,current.size())if(num[current[i]-'0']==0)return "INVALID INPUT";
if(current[0]=='0')return "INVALID INPUT";
for(int i=current.size()-1;i>=0;i--){
int cur=current[i]-'0';
for(int j=cur+1;;j++){
if(num[j%10]){
current[i]=(j%10)+'0';
if(j%10>cur)return current;
break;
}
}
}
char ch;
FORE(i,1,10)if(num[i]){
ch=i+'0';
break;
}
return ch+current;
}
};
