TopCoder SRM 486 DIV 2

Problem	Check	Points
250	◯	182.73
500	×	-
1000	-	-

Rating 401 -> 622

とりあえず250解けたのでよかった。
500はif文をelse ifと書いていただけの残念すぎる間違い。

Probelm 250 TxMsg

問題

Strange abbreviations are often used to write text messages on uncomfortable mobile devices. One particular strategy for encoding texts composed of alphabetic characters and spaces is the following:

• Spaces are maintained, and each word is encoded individually. A word is a consecutive string of alphabetic characters.
• If the word is composed only of vowels, it is written exactly as in the original message.
• If the word has at least one consonant, write only the consonants that do not have another consonant immediately before them. Do not write any vowels.
• The letters considered vowels in these rules are 'a', 'e', 'i', 'o' and 'u'. All other letters are considered consonants.

For instance, "ps i love u" would be abbreviated as "p i lv u" while "please please me" would be abbreviated as "ps ps m".
You will be given the original message in the string original. Return a string with the message abbreviated using the described strategy.

My code

bool isVowel(char c){
	if(c=='a' || c=='e' || c=='i' || c=='o' || c=='u') return true;
	return false;
}

string retStr(string s){
	bool flag = true;
	for(int i=0 ; i<s.size() ; i++){
		if(!isVowel(s[i])) flag = false;
	}

	if(flag) return s;

	string ret;
	for(int i=0 ; i<s.size() ; i++){
		if(isVowel(s[i])) continue;

		if(i==0){
			ret += s[i];
			continue;
		}

		if(isVowel(s[i-1])) ret += s[i];
	}
	return ret;
}

vector<string> split(string str){
	stringstream s(str);

	string item;
	vector<string> result;
	while(s >> item){
		result.push_back(item);
	}
	return result;
}

class TxMsg {
public:
  string getMessage(string original) {
	vector<string> vs = split(original);

	string s;
	for(int i=0 ; i<vs.size() ; i++){ 
		s += retStr(vs[i]);
		if(i!=vs.size()-1) s +=" ";
	}

    return s;
  }
};

Problem 500 OneRegister

問題

You've designed a computer and implemented all the common arithmetic operators: addition, subtraction, multiplication and integer division. However, your budget was very limited, so you could only afford to place a single register in the computer. The register can store any non-negative integer value. Since there is only one register, there is no need to identify the store location or the operands of each operation or its result. The programming language has four instructions: '+', '-', '*' and '/'. Each instruction performs the corresponding operation using the value in the register as both its parameters. It then stores the result in the same register, overwriting the previous content.
A program for your computer is a sequential list of zero or more instructions. You want to show that, even with its limitations, your newly constructed computer is powerful. You will be given two ints s and t. Return the shortest program that finishes with a value of t in the register if it contained s before executing. If there is more than one possible answer, return the one that comes earliest lexicographically. If there is no program that can do the job, return ":-(" (quotes for clarity) instead.

My code

set<string> ans;
ll gt;
ll mindig;
deque<ll> deqnum;
deque<string> deqstr;

void bfs(ll n, string op){
	ll num;
	string str;

	deqnum.push_back(n);
	deqstr.push_back(op);

	while(!deqnum.empty()){
		num = deqnum[0];
		str = deqstr[0];

		deqnum.pop_front();
		deqstr.pop_front();

		if(mindig < str.size()) break;

		if(num==gt){
			if(mindig > str.size()){
				mindig = str.size();
				ans.clear();
			}
			ans.insert(str);
			continue;
		}

		if(str==""){
			deqnum.push_back(1);
			deqstr.push_back("/");
		}

		if(num<gt){
			deqnum.push_back(num*2);
			deqstr.push_back(str+"+");

			if(num!=1){
				deqnum.push_back(num*num);
				deqstr.push_back(str+"*");
			}
		}	
	}
}

class OneRegister {
public:
  string getProgram(int s, int t) {

	if(t==0) return "-";
	if(s==t) return "";

	ans.clear();
	gt = (ll)t;
	mindig = (ll)99999999;

	bfs(s,"");

	if(mindig==99999999) return ":-(";
	return *ans.begin();
  }
};