// 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)”