hackercupai/hackercup

1// Jammin'2// Solution by Jacob Plachta3 4#define DEBUG 05 6#include <algorithm>7#include <functional>8#include <numeric>9#include <iostream>10#include <iomanip>11#include <cstdio>12#include <cmath>13#include <complex>14#include <cstdlib>15#include <ctime>16#include <cstring>17#include <cassert>18#include <string>19#include <vector>20#include <list>21#include <map>22#include <set>23#include <deque>24#include <queue>25#include <stack>26#include <bitset>27#include <sstream>28using namespace std;29 30#define LL long long31#define LD long double32#define PR pair<int,int>33 34#define Fox(i,n) for (i=0; i<n; i++)35#define Fox1(i,n) for (i=1; i<=n; i++)36#define FoxI(i,a,b) for (i=a; i<=b; i++)37#define FoxR(i,n) for (i=(n)-1; i>=0; i--)38#define FoxR1(i,n) for (i=n; i>0; i--)39#define FoxRI(i,a,b) for (i=b; i>=a; i--)40#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)41#define Min(a,b) a=min(a,b)42#define Max(a,b) a=max(a,b)43#define Sz(s) int((s).size())44#define All(s) (s).begin(),(s).end()45#define Fill(s,v) memset(s,v,sizeof(s))46#define pb push_back47#define mp make_pair48#define x first49#define y second50 51template<typename T> T Abs(T x) { return(x<0 ? -x : x); }52template<typename T> T Sqr(T x) { return(x*x); }53string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }54 55const int INF = (int)1e9;56const LD EPS = 1e-12;57const LD PI = acos(-1.0);58 59#if DEBUG60#define GETCHAR getchar61#else62#define GETCHAR getchar_unlocked63#endif64 65bool Read(int &x)66{67	char c,r=0,n=0;68	x=0;69		for(;;)70		{71			c=GETCHAR();72				if ((c<0) && (!r))73					return(0);74				if ((c=='-') && (!r))75					n=1;76				else77				if ((c>='0') && (c<='9'))78					x=x*10+c-'0',r=1;79				else80				if (r)81					break;82		}83		if (n)84			x=-x;85	return(1);86}87 88#define LIM 40000489 90int main()91{92		if (DEBUG)93			freopen("in.txt","r",stdin);94	// vars95	int T,t;96	int N;97	int i,ans,cur,numPast;98	bool pastReachable;99	static char C[LIM];100	// testcase loop101	Read(T);102		Fox1(t,T)103		{104			// input105			scanf("%s",&C);106			N=strlen(C);107			// simulate108			ans=cur=numPast=pastReachable=0;109				Fox(i,N)110					if (C[i]=='*') // jammer111					{112						cur++; // pick it up113							if ((cur>=2) || (pastReachable)) // reclaim all past jammers114							{115								cur+=numPast;116								numPast=pastReachable=0;117							}118						Max(ans,cur); // new best?119					}120					else121					if ((C[i]=='#') && (C[i+1]!='#')) // 1 barrier122					{123						// can cross totally for free?124							if (cur>=2)125								continue;126						// can cross for free, but while making a past jammer unreachable?127							 if (C[i+1]=='*')128							 {129								 pastReachable=0;130								 continue;131							 }132						// can cross using a jammer?133							if (cur)134							{135								cur--;136								numPast++,pastReachable=1;137								continue;138							}139						// can't cross140						break;141					}142					else143					if ((C[i]=='#') && (C[i+1]=='#') && (C[i+2]!='#')) // 2 barriers144					{145						// can cross by swapping out for a jammer on the other side?146							if ((cur) && (C[i+2]=='*'))147							{148								i+=2;149								continue;150							}151						// can't cross152						break;153					}154					else155					if ((C[i]=='#') && (C[i+1]=='#') && (C[i+2]=='#')) // 3+ barriers156						break; // can never cross157			// output158			printf("Case #%d: %d\n",t,ans);159		}160	return(0);161}