#include "hiccup.h"
static bool able(int& dep, std::string a, int x);
static bool dfs(int &dep, std::string a, int x, int state)
{
//printf("%d %d %d ", dep, x, state);
//if (dep < a.size())printf("%c", a[dep]);
//else printf("\\");
//printf("\n");
if (dep == a.size())return (state == (x+2));
if (state == x + 2)
{
return true;
}
if (state == 1) {
while (a[dep] != 'C')
{
if (a[dep] == 'H')
{
if (!able(dep, a, x))
return false;
}
else
{
dep++;
}
}
if (a[dep] == 'C') {
dep++;
return dfs(dep, a, x, 2);
}
}
else {
while (a[dep] != '!')
{
if (a[dep] == 'H')
{
if (!able(dep, a, x))
return false;
}
else
return false;
}
if (a[dep] == '!')
{
dep++;
return dfs(dep, a, x, state + 1);
}
}
}
static bool able(int& dep, std::string a, int x)
{
//printf("-cur dep : %d\n", dep);
if (a[dep] == 'H')
{
dep++;
if (!dfs(dep, a, x, 1))
return false;
}
else if (a[dep] == 'C')
{
return false;
}
return true;
}
static bool able2(int &dep, std::string a, int x)
{
while (dep < a.size())
{
//printf("cur dep : %d\n", dep);
if (a[dep] == 'H')
{
dep++;
if (!dfs(dep, a, x, 1))
return false;
}
else if(a[dep] == 'C')
return false;
else {
dep++;
}
}
return true;
}
int HicCup(std::string a) {
int n = a.size();
int i, j, k;
for (i = j=k=0; i < n; i++) {
if (a[i] == 'H') {
k++; j = 0;
}
else if (a[i] == 'C') { k--; j = 1; if (k < 0)return -1; }
else {
if (j == 0)return -1;
}
}
if (k > 0) return -1;
int l = 1;
int r = n;
while (l < r) {
int mid = (l + r) / 2;
int dep = 0;
//printf("try %d\n", mid);
if (able2(dep, a, mid))
{
l = mid + 1;
}
else
r = mid;
}
return l-1;
}
