#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
void Anna(int N, std::vector<char> S) {
for (char c : S){
if (c == 'X'){
Send(0);
Send(0);
}
else if (c == 'Y'){
Send(0);
Send(1);
}
else{
Send(1);
Send(0);
}
}
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
const int NM = 18;
string S;
int dp[NM+5][NM+5];
void trace(int i, int j){
if (i > j) return;
if (i == j){
Remove(i);
return;
}
if (dp[i][j] == dp[i+1][j]){
Remove(i);
trace(i+1, j);
return;
}
if (dp[i][j] == dp[i][j-1]){
trace(i, j-1);
Remove(j);
return;
}
for (int k = i+1; k < j; k++){
if (S[k] != 'Y') continue;
if (1+(i+1 <= k-1 ? dp[i+1][k-1] : 0)+(k+1 <= j-1 ? dp[k+1][j-1] : 0) != dp[i][j]) continue;
trace(i+1, k-1);
trace(k+1, j-1);
Remove(k);
Remove(i);
Remove(j);
break;
}
}
void Bruno(int N, int L, std::vector<int> A) {
assert(L == 2*N);
S = "";
for (int i = 0; i < L; i += 2){
if (A[i] == 0 && A[i+1] == 0) S.push_back('X');
else if (A[i] == 0 && A[i+1] == 1) S.push_back('Y');
else S.push_back('Z');
}
for (int i = 0; i < N; i++) dp[i][i] = 0;
for (int i = N-1; i >= 0; i--)
for (int j = i+1; j < N; j++){
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
if (S[i] == 'X' && S[j] == 'Z'){
for (int k = i+1; k < j; k++){
if (S[k] != 'Y') continue;
dp[i][j] = max(dp[i][j], 1+(i+1 <= k-1 ? dp[i+1][k-1] : 0)+(k+1 <= j-1 ? dp[k+1][j-1] : 0));
}
}
}
trace(0, N-1);
}
