#include "hiccup.h"
using namespace std;
int valid(const string& S) {
int h = 0, th = 0;
for (char ch : S) {
if (ch == 'H') h++, th++;
if (ch == 'C') {
if (h == 0) return 0;
h--;
}
if (ch == '!') continue;
}
return (h == 0 && th > 0);
}
int check(int x, const string& S) {
int h = 0, sign = 0;
for (char ch : S) {
if (ch == 'H') h++;
else if (ch == 'C') h--, sign += x;
else {
sign--;
if (sign < 0) sign = 0;
}
}
return sign == 0;
}
int HicCup(std::string S) {
int cntH = 0, cntSign = 0;
if (!valid(S)) return -1;
for (char ch : S) cntH += ch == 'H', cntSign += ch == '!';
int lo = 0, hi = cntSign/cntH;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (check(mid, S)) lo = mid;
else hi = mid - 1;
}
return lo;
}
