[Qualification Round 2018] Saving The Universe Again : https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard

Saving The Universe Again.cc

//
//  Created by fpdjsns on 2019. 1. 21
//  Copyright © 2019 fpdjsns. All rights reserved.
//

/*
 * 시간복잡도 : O(T * |P|^2)
 * 공간복잡도 : O(|P|)
 */

#include<iostream>
#include<string>
#include<map>
#include<algorithm>

using namespace std;

int main() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		int D;
		cin >> D;

		string P;
		cin >> P;

		int sCnt = 0;
		long long int power = 1;
		long long int damage = 0;

		map<long long int, int> m; // (damage, cnt)
		long long int maxShootDamage = 1;

		for (int i = 0; i < P.size(); i++) {
			if (P[i] == 'S') { // S
				sCnt++;
				damage += power;
				maxShootDamage = max(maxShootDamage, power);
				m[power]++;
			}
			else { // C
				power *= 2;
			}
		}

		printf("Case #%d: ", t);
		if (sCnt > D) {
			printf("IMPOSSIBLE\n");
			continue;
		}

		int hackCnt = 0;

		while (D < damage) {
			hackCnt++;
			damage -= maxShootDamage / 2;
			m[maxShootDamage]--;
			m[maxShootDamage / 2]++;
			if (m[maxShootDamage] == 0) {
				maxShootDamage /= 2;
			}
		}

		printf("%d\n", hackCnt);

	}
	return 0;
}