首页 > itarticle > codejam 2017 qualification oversized pancake flipper

codejam 2017 qualification oversized pancake flipper

admin 11月 12, 2020 0

Problem

题目大意

桌面上有S (S <= 1000) 枚硬币排成一行，每次可以翻转连续的K枚硬币（只改变正反状态，不改变相对顺序），求从一个初始状态到另一个状态的最少翻转次数。

Analysis

pancake的正反状态，仅由初始状态和反转次数决定

Code in C++

int () {
	int T;
	string s;
	int K;
	int ans;
	cin >> T;
	FOR(kase, 0, T){
		cout << "Case #" << kase + 1 << ": ";
		cin >> s >> K;
		ans = 0;
		FOR(i, 0, s.length() - K + 1) {
			if (s[i] == '-'){
				ans ++;
				FOR(j, i, i+K)
					s[j] = '-' + '+' - s[j];
			}
		}
		if (s != string(s.length(), '+'))
			cout << "IMPOSSIBLE" << endl;
		else
		 	cout << ans << endl;
	}
	return 0;
}