SRM 310 Div2 Medium InputBoxChecker

問題

電卓で数字が途中まで入力されてる。
その後数字を続けて入力して、smallest以上largest以下の数にできるか答えよ。

制約条件

smallest, largest≦20億

方針

途中まで入力された数字がsmallestまたはlargestの接頭辞になっていたら、
smallestまたはlargestを入力できるのでOK.

そうでないとき、greedyに0を末尾に付け足していって、
smallest以上largest以下になっているかを見ればいい。

言われてみると確かにそうだけどこんなの思いつかない……

ソースコード

string tos(int n){stringstream ss; ss<<n; return ss.str();}
bool ge(string a,string b){
	return a.size()<b.size()||a.size()==b.size()&&a<=b;
}

string s,l;
bool ok(int n){
	string a=tos(n);
	
	if(a.size()<=s.size()&&s.substr(0,a.size())==a||
		a.size()<=l.size()&&l.substr(0,a.size())==a)return 1;
	
	while(a.size()<=l.size()){
		if(ge(s,a)&&ge(a,l))return 1;
		a.pb('0');
	}
	return 0;
}
class InputBoxChecker {
	public:
	vector <string> checkPrefix(int smallest, int largest, vector <int> numbers) 
	{
		s=tos(smallest); l=tos(largest);
		
		vs ans;
		rep(i,numbers.size())ans.pb(ok(numbers[i])?"VALID":"INVALID");
		return ans;
	}
};