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

One thought on “UVa : 11586 (Train Tracks)

  1. MF and FM are actually same pieces 
    u can use them alternatively 
    if u turn over the MF piece then u'll get a FM pieces 
    
    Critical Input : 
    11
    MF FM FM MF
    MM
    FF
    MF
    FM
    MF FM
    FF MM
    MM FF FM
    MF MF MF
    MF MF MF MM
    FF MF MF FF
    
    Output : 
    LOOP
    NO LOOP
    NO LOOP
    NO LOOP
    NO LOOP
    LOOP
    LOOP
    LOOP
    LOOP
    NO LOOP
    NO LOOP
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s