/* -*- coding: utf-8 -*- * * 3299.cc: No.3299 K-th MMA String - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100000; const int MAX_M = 30; /* typedef */ /* global variables */ int dp0[MAX_M + 1][4], dp1[MAX_M + 1][2]; /* subroutines */ /* main */ int main() { int n, k; scanf("%d%d", &n, &k); k--; dp0[0][3] = 1; int m = 0; for (int i = 0; i < MAX_M; i++) { for (int j = 0; j < 4; j++) { if (dp0[i][j]) { for (int b = 0; b < 2; b++) { int msk = (j << 1) | b, j1 = msk & 3; if (msk == 3) dp1[i + 1][b] += dp0[i][j]; else dp0[i + 1][j1] += dp0[i][j]; } } } for (int b = 0; b < 2; b++) dp1[i + 1][b] += dp1[i][0] + dp1[i][1]; if (dp1[i + 1][0] + dp1[i + 1][1] > k) {m = i + 1; break;} } //printf(" m=%d: %d,%d\n", m, dp1[m][0], dp1[m][1]); for (int i = n; i > m; i--) putchar('A'); for (int i = m, msk = 0, f = 0; i > 0; i--) { msk = (msk << 1) & 7; if (msk == 6) f = 1; int di = f ? (1 << (i - 1)) : dp1[i][0]; if (k < di) putchar('A'); else { putchar('M'); k -= di; msk |= 1; } } putchar('\n'); return 0; }