#include "hiccup.h"
#include <stack>
using namespace std;
struct State {
int cur_state = 0;
int want = 0;
int closed = 0;
// 0 = need C, 1 = need !
int update(char ch) {
if (ch == 'C' && cur_state == 0) {
cur_state = 1;
return 1;
}
if (ch == '!' && cur_state == 1) {
want--;
return 1;
}
return 0;
}
};
int check(int x, const string& S) {
if (x == -1) return 1;
stack<State> ST;
int closed = 0;
for (char ch : S) {
//printf("processing %d, %c\n", x, ch);
if (ch == 'H') {
ST.push(State());
ST.top().want = x;
continue;
}
else if (ch == 'C') {
if (ST.empty()) return 0;
if (!ST.top().update(ch)) return 0;
if (ST.top().want == 0) {
ST.pop();
if (ST.empty()) closed = 1;
else ST.top().closed = 1;
//printf("Popped\n");
}
}
else {
if (ST.empty() && !closed) return 0;
if (ST.empty() && closed) {
//printf("consumed\n");
continue;
}
if (!ST.top().update(ch)) {
if (ST.top().closed) {
//printf("consumed\n");
continue;
}
return 0;
}
if (ST.top().want == 0) {
ST.pop();
if (ST.empty()) closed = 1;
else ST.top().closed = 1;
//printf("Popped\n");
}
}
}
return ST.empty();
}
int HicCup(std::string S) {
int cntH = 0, cntSign = 0;
for (char ch : S) cntH += ch == 'H', cntSign += ch == '!';
int lo = -1, hi = cntSign/cntH;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (check(mid, S)) lo = mid;
else hi = mid - 1;
}
return lo;
}
