{"problem":{"name":"C. Сейф","description":{"content":"Сокровища короны скрыты в сейфе, который находится под наблюдением охраны. Однако охранник время от времени отходит на перерыв, и у грабителя Буратино появляется шанс взломать сейф. Полистав «Справоч","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10096C"},"statements":[{"statement_type":"Markdown","content":"Сокровища короны скрыты в сейфе, который находится под наблюдением охраны. Однако охранник время от времени отходит на перерыв, и у грабителя Буратино появляется шанс взломать сейф.\n\nПолистав «Справочник юного взломщика», Буратино узнал, что код к сейфам подобной конструкции обязательно удовлетворяет грамматике, определяемой следующей формой Бэкуса-Наура:\n\nДругими словами, если c — произвольный корректный код, то AcX и BcY — также корректный код; кроме того, если c1 и c2 — произвольные корректные коды, то c1c2 — также корректный код.\n\nТакже Буратино выяснил, что код данного конкретного сейфа должен состоять ровно из N символов. В момент, когда в сейф положили сокровища и закрыли его дверцу, значение кода было следующим:\n\nЗатем каждую секунду код изменялся на лексикографически минимальный корректный код, больший текущего, а в том случае, если текущий код являлся максимально возможным, — на показанный выше стартовый код.\n\nБуратино тщательно замерил время, прошедшее с момента закрытия дверцы сейфа. Помогите ему подобрать код к сейфу.\n\nВвод содержит целое чётное число N и целое число T (2 ≤ N ≤ 30, 0 ≤ T ≤ 1018) — соответственно длину кода и количество секунд, прошедших с момента закрытия сейфа.\n\nВыведите строку, состоящую из N символов 'A', 'X', 'B', 'Y', — код к сейфу в момент времени T.\n\n## Входные Данные\n\nВвод содержит целое чётное число N и целое число T (2 ≤ N ≤ 30, 0 ≤ T ≤ 1018) — соответственно длину кода и количество секунд, прошедших с момента закрытия сейфа.\n\n## Выходные Данные\n\nВыведите строку, состоящую из N символов 'A', 'X', 'B', 'Y', — код к сейфу в момент времени T.\n\n## Примеры\n\nВходные данные6 0Выходные данныеAAAXXXВходные данные6 1Выходные данныеAABYXXВходные данные6 2Выходные данныеAAXAXXВходные данные6 3Выходные данныеAAXBYXВходные данные6 4Выходные данныеAAXXAXВходные данные6 10Выходные данныеABYXAX\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $\\Sigma = \\{A, X, B, Y\\}$.  \nLet $L \\subseteq \\Sigma^*$ be the language generated by the grammar:  \n- Base: $\\varepsilon \\in L$  \n- Rules: If $c \\in L$, then $AcX \\in L$ and $BcY \\in L$  \n- Concatenation: If $c_1, c_2 \\in L$, then $c_1c_2 \\in L$  \n\nLet $L_N = \\{ w \\in L \\mid |w| = N \\}$ be the set of valid codes of length $N$.  \n\n**Constraints**  \n1. $N \\in 2\\mathbb{Z}$, $2 \\leq N \\leq 30$  \n2. $T \\in \\mathbb{Z}$, $0 \\leq T \\leq 10^{18}$  \n3. The initial code at $T=0$ is the lexicographically smallest element of $L_N$.  \n\n**Objective**  \nGiven $N$ and $T$, find the $T$-th code in the cyclic lexicographically ordered sequence of $L_N$, where:  \n- The sequence starts at the lex-minimal code in $L_N$  \n- Each subsequent code is the lexicographically next valid code in $L_N$  \n- After the lex-maximal code, the sequence wraps to the lex-minimal code  \n\nOutput the code at time $T$:  \n$$\n\\text{code}(T) = \\text{the } (T \\bmod |L_N|)\\text{-th element in the lex-ordered list of } L_N\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10096C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}