SRM 504 250pt: MathContest

keyword

シミュレーション　C++

問題概要

スタックに黒と白のボールが10^6個積まれている。一番上のボールを捨てる。捨てたボールが

• 黒: スタック内のボールの色を反転させる。
• 白: スタック内のボールの順序を逆にする。

スタックが空になるまで繰り返す。捨てた黒いボールの数を求める問題。

解法

シミュレーションするだけ(さすがに真面目に順序を入れ替えたりフリップさせていたらTLEするが)。dequeを使うと楽だった。

class MathContest {
public:
int countBlack(string ballSequence, int repetitions) {
	deque<int> Q;
	cout << ballSequence.length() << endl;
	for(int i=0; i<repetitions; i++){
		for(int j=0; j<(int)ballSequence.length(); j++){
			Q.push_back(ballSequence[j] == 'B' ? 1 : 0);
		}
	}
	bool black = true, order = true;
	int ret = 0;
	while(!Q.empty()){
		int tp = order?Q.front():Q.back();
		if(order){
			Q.pop_front();
		}
		else{
			Q.pop_back();
		}
		if(black ^ (tp==0)){
			ret++;
			black = !black;
		}
		else{
			order = !order;
		}
	}
	return ret;
}