# Cod sursa(job #1606114)

Utilizator Data 19 februarie 2016 21:17:40 Perle 100 cpp done Arhiva de probleme 2.64 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <stack>

using namespace std;
const int nmax = 10003;
stack<int > q;
int a[nmax];
int n;

////////////////////////////////// Methoda 1 /////////////////////////////////////////
// Let A = 10 B = 11 and C = 12

/*
bool res(int len) {
int ind = 0, curr;
bool ended = false;

while (ind < len && !ended) {
curr = q.top();
q.pop();
switch (curr)
{
case 1:
case 2:
case 3:
if (curr != a[ind]) ended = true;
break;
case 11:
if (a[ind] == 2)
q.push(11);			// b
else if (a[ind] == 1) {
q.push(12);			// c
q.push(10);			// a
q.push(3);			// 3
q.push(10);			// a
}
else ended = true;
break;
case 12 :
if (a[ind] == 1) {
q.push(10);			// a
q.push(2);			// 2
}
else if (a[ind] == 3) {
q.push(12);			// C
q.push(11);			// B
}
break;
}
ind++;
}

if (ind == len && ended == false && q.empty())
return true;
return false;
}

int main(){
freopen("perle.in", "r", stdin);
freopen("perle.out", "w", stdout);
scanf("%d", &n);

int len;
bool ok;
for (int i = 0; i < n; i++){
scanf("%d", &len);
for (int j = 0; j < len; j++)
scanf("%d", &a[j]);
a[len] = 7;		// end point
ok = false;

// test with starting A
if (len == 1)
ok = true;
else if (a[0] == 2) {
q.push(11);					// 2B
ok = res(len);
}
else if (a[0] == 3) {
q.push(12);					// 3BC
ok = res(len);
}
else if (a[0] == 1 && len == 3) {
if (a[1] == 2) ok = true;
}
else {
q.push(11);				// 1A3AC
ok = res(len);
}

printf("%d\n", ok);
}

fclose(stdin);
fclose(stdout);
return 0;
}
*/
/////////////////////////////////////////////////// Methoda 2 /////////////////////////////

int C(int k);

int B(int k) {
if (a[k] == 2)
return	B(k + 1);
else if (a[k] == 1 && a[k + 2] == 3)
return C(k + 4);
return 0;
}

int C(int k) {
if (a[k] == 1 && a[k + 1] == 2) return k + 3;
else if (a[k] == 3)				return C(B(k + 1));
else if (a[k] == 2)				return k + 1;
return 0;
}

int main(){
freopen("perle.in", "r", stdin);
freopen("perle.out", "w", stdout);
scanf("%d", &n);

int len, dis;
for (int i = 0; i < n; i++){
scanf("%d", &len);
for (int j = 0; j < len; j++)
scanf("%d", &a[j]);
a[len] = 7;		// end point

if (len == 1)					dis = 1;
else if (a[0] == 2)				dis = B(0);
else if (a[0] == 3)				dis = C(0);
else if (a[0] == 1 && len == 3) dis = C(0);
else							dis = B(0);

printf("%d\n", dis == len ? 1 : 0);
}

fclose(stdin);
fclose(stdout);
return 0;
}