Problem: jammin (2018 round3)

Uriel is an android programmed for a singular purpose — to obtain jam. He's
found himself in a row of cells, some of which hopefully contain raspberry jam
for him to gather in the form of special jars called "jammers".

There are |**C**| cells in the row, and their contents are described by a
string **C**, with the _i_th character of **C** corresponding to the _i_th
cell. Each character is one of the following:

  * \- "`.`": Empty cell 
  * \- "`*`": Cell initially containing a jammer 
  * \- "`#`": Cell containing a laser barrier 

By default, each laser barrier is "active". However, whenever a laser barrier
has at least one jammer in an adjacent cell to its left or right, that laser
barrier becomes jammed by the jammer's jam, and becomes "inactive" instead. A
laser barrier may switch back and forth between being inactive and active if
jammers next to it are added or removed. A single jammer may be responsible
for jamming multiple laser barriers at once.

Uriel begins in the first cell (which is guaranteed to be empty). He has the
ability to carry around any number of jammers at once, though he initially has
0 of them. At each point in time, he may choose to perform one of the
following actions:

  * \- Pick up a jammer from his current cell. He may only do so if the cell contains a jammer. That cell will then become empty.
  * \- Place one of his jammers into his current cell. He may only do so if he's holding at least one jammer, and if the cell is currently completely empty (it doesn't contain another jammer, and doesn't contain a laser barrier, even if it's inactive).
  * \- Walk left or right into an adjacent cell, without leaving the row of cells. He may only do so if that cell doesn't currently contain an active laser barrier.

Uriel isn't interested in consuming any jam, he just wants to hold onto it —
onto as much of it as he can. As such, he'd like to determine the maximum
number of jammers which he can ever end up holding at a single time, after
performing any number of moves of his choice.

### Input

Input begins with an integer **T**, the number of rows of cells. For each row
of cells, there is a single line containing the string **C** as described
above.

### Output

For the _i_th row of cells, output a line containing "Case #_i_: " followed by
the maximum number of jammers which Uriel can end up holding at once.

### Constraints

1 ≤ **T** ≤ 100  
1 ≤ |**C**| ≤ 400,000  

### Explanation of Sample

In the first case, there are no laser barriers, so Uriel can simply walk to
the right while picking up each jammer he comes across, allowing him to end up
with 5 jammers by the end.

In the second case, Uriel is immediately left with no valid moves, as there's
an active laser barrier to his right and he's not holding any jammers.

In the third case, the first laser barrier which Uriel encounters is already
inactive due to the jammer to its right, meaning that he can walk through it.
The second laser barrier is initially active, but Uriel can jam it by putting
down a jammer to its left. After collecting the rightmost jammer, Uriel can
return to pick up the jammer that he previously put down to end up with all 5
jammers simultaneously in his possession.



Sample input:
7
...**.*..*....*..
.#.**.*..*....*..
..#**.*..*.#..*..
.*#*####*#
.*#.*#.*#.*#.*
..*.#.#*##*.#.#*#..#*..#.#*.#*##*##.*#*#..##*#*
...*.##*##*.#..#*.#..#*.#.#.*##*.#.#*..*##*.#*#


Sample output:
Case #1: 5
Case #2: 0
Case #3: 5
Case #4: 2
Case #5: 5
Case #6: 6
Case #7: 1



Code: // Jammin'
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 400004

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N;
	int i,ans,cur,numPast;
	bool pastReachable;
	static char C[LIM];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			scanf("%s",&C);
			N=strlen(C);
			// simulate
			ans=cur=numPast=pastReachable=0;
				Fox(i,N)
					if (C[i]=='*') // jammer
					{
						cur++; // pick it up
							if ((cur>=2) || (pastReachable)) // reclaim all past jammers
							{
								cur+=numPast;
								numPast=pastReachable=0;
							}
						Max(ans,cur); // new best?
					}
					else
					if ((C[i]=='#') && (C[i+1]!='#')) // 1 barrier
					{
						// can cross totally for free?
							if (cur>=2)
								continue;
						// can cross for free, but while making a past jammer unreachable?
							 if (C[i+1]=='*')
							 {
								 pastReachable=0;
								 continue;
							 }
						// can cross using a jammer?
							if (cur)
							{
								cur--;
								numPast++,pastReachable=1;
								continue;
							}
						// can't cross
						break;
					}
					else
					if ((C[i]=='#') && (C[i+1]=='#') && (C[i+2]!='#')) // 2 barriers
					{
						// can cross by swapping out for a jammer on the other side?
							if ((cur) && (C[i+2]=='*'))
							{
								i+=2;
								continue;
							}
						// can't cross
						break;
					}
					else
					if ((C[i]=='#') && (C[i+1]=='#') && (C[i+2]=='#')) // 3+ barriers
						break; // can never cross
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}