ABC E求调

#include <bits/stdc++.h>
using namespace std;

#ifdef SPN_LOCAL
#define debug(x) (cerr << "On Line " << __LINE__ << ": " << #x << " = " << x << endl)
#else
#define debug(x)
#endif

#define int long long
const int N = 6e6 + 5;

int n, m, a[N];
char c;

int v[15][N];

int dfs1(int d, int x) {
	if (d == 0) return v[d][x] = a[x];
	vector<int> vec = {dfs1(d - 1, 3 * x - 2), dfs1(d - 1, 3 * x - 1), dfs1(d - 1, 3 * x)};
	sort(vec.begin(), vec.end());
	if (vec[0] == 0 && vec[1] == 0) v[d][x] = 0;
	else v[d][x] = 1;
	return v[d][x];
}

int dfs(int d, int x, int s) {
	// 第d步，使a2[x]改变为s的最小步数
	if (d == 0) return a[x] != s;
	vector<int> vec = {dfs(d - 1, 3 * x - 2, v[d - 1][3 * x - 2] ^ 1), 
		dfs(d - 1, 3 * x - 1, v[d - 1][3 * x - 1] ^ 1), 
		dfs(d - 1, 3 * x, v[d - 1][3 * x] ^ 1)};
	sort(vec.begin(), vec.end());
	if (v[d - 1][3 * x - 2] == v[d - 1][3 * x - 1] && v[d - 1][3 * x - 1] == v[d - 1][3 * x]) {
		return vec[0] + vec[1];
	}
	return vec[0];
}

void _main() {
	cin >> n;
	m = pow(3, n);
	for (int i = 1; i <= m; i++) cin >> c, a[i] = c - '0';
	dfs1(n, 1);
//	for (int i = 0; i <= n; i++) {
//		for (int j = 1; j <= m; j++) cerr << v[i][j];
//		cerr << endl;
//	}
	cout << dfs(n, 1, v[n][1] ^ 1);
} signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
	
	int t = 1; for (/*cin >> t*/; t--; ) _main();
	return 0;
}