UVa : 11586 (Train Tracks)

// http://uva.onlinejudge.org/external/115/11586.html

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

int MM, FF, mixed;
int cnt;
bool res;

void bktk (int at, char startsWith, char last)
{
	if ( at == cnt ) {
		if ( last != startsWith ) res = true;
		return;
	}

	if ( startsWith == 'Z' ) { // run only once, first time only 
		if ( MM ) { MM--; bktk (at + 1, 'M', 'M'); MM++; }
		if ( FF ) { FF--; bktk (at + 1, 'F', 'F'); FF++; }
		if ( mixed ) { mixed--; bktk (at + 1, 'M', 'F'); mixed++; }
		if ( mixed ) { mixed--; bktk (at + 1, 'F', 'M'); mixed++; }
		return;
	}

	if ( last == 'M' ) {
		if ( FF ) { FF--; bktk (at + 1, startsWith, 'F'); FF++; }
		if ( mixed ) { mixed--; bktk (at + 1, startsWith, 'M'); mixed++; }
	}
	else {
		if ( MM ) { MM--; bktk (at + 1, startsWith, 'M'); MM++; }
		if ( mixed ) { mixed--; bktk (at + 1, startsWith, 'F'); mixed++; }
	}
}

int main ()
{
	int testCase;
	scanf ("%d", &testCase);
	getchar ();

	while ( testCase-- ) {
		char input [1000];
		gets (input);

		res = false;
		MM = FF = mixed = cnt = 0;

		char *pch;
		pch = strtok (input, " ");

		while ( pch != NULL ) {
			if ( strcmp (pch, "MM") == 0 ) MM++;
			else if ( strcmp (pch, "FF") == 0 ) FF++;
			else  mixed++;
			pch = strtok (NULL, " ");
			cnt++;
		}

		if ( cnt == 1 ) { printf ("NO LOOP\n"); continue; }

		bktk (0, 'Z', 'Z');

		if ( res == true ) printf ("LOOP\n");
		else printf ("NO LOOP\n");
	}

	return 0;
}

// @END_OF_SOURCE_CODE

Advertisements