{"problem":{"name":"A. Tritwise Mex","description":{"content":"Let us denote $\"mex\"(a, b)$ (minimum excludant) as the minimum non-negative integer which is neither equal to $a$ nor equal to $b$. It always holds that $\"mex\"(a, b) < 3$, thus we can define tritwise ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10212A"},"statements":[{"statement_type":"Markdown","content":"Let us denote $\"mex\"(a, b)$ (minimum excludant) as the minimum non-negative integer which is neither equal to $a$ nor equal to $b$. It always holds that $\"mex\"(a, b) < 3$, thus we can define tritwise mex. If we write $a$ and $b$ in ternary notation: $$a = \\sum\\limits_{i=0}^{k-1}a_i \\cdot 3^i,~~b=\\sum\\limits_{i=0}^{k-1} b_i \\cdot 3^i\\text{,}$$ where $a_i$ and $b_i$ are integers from $0$ to $2$, we define $upright(m e x)_3$ as follows: $$\\mathrm{mex}_3(a, b) = \\sum\\limits_{i=0}^{k-1}\\mathrm{mex}(a_i,b_i) \\cdot 3^i\\text{.}$$ You are given two sequences $a_0, \\\\dots, a_(3^k -1)$ and $b_0, \\\\dots, b_(3^k -1)$. You have to compute the sequence $c_0, \\\\dots, c_(3^k -1)$: $$c_k = \\sum\\limits_{\\mathrm{mex}_3(i,j)=k}a_i \\cdot b_j\\text{.}$$\n\nThe first line of input contains a single integer $k$ ($1 <= k <= 12$).\n\nThe second line of input contains $3^k$ integers $a_0, \\\\dots, a_(3^k -1)$ ($0 <= a_i <= 10^3$).\n\nThe third line of input contains $3^k$ integers $b_0, \\\\dots, b_(3^k -1)$ ($0 <= b_i <= 10^3$).\n\nOutput $3^k$ integers $c_0, \\\\dots, c_(3^k -1)$ separated by spaces.\n\nFor reference: $3^(12) = 531 thin 441$.\n\n## Input\n\nThe first line of input contains a single integer $k$ ($1 <= k <= 12$).The second line of input contains $3^k$ integers $a_0, \\\\dots, a_{3^k -1}$ ($0 <= a_i <= 10^3$).The third line of input contains $3^k$ integers $b_0, \\\\dots, b_{3^k -1}$ ($0 <= b_i <= 10^3$).\n\n## Output\n\nOutput $3^k$ integers $c_0, \\\\dots, c_{3^k -1}$ separated by spaces.\n\n[samples]\n\n## Note\n\nFor reference: $3^(12) = 531 thin 441$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq 12 $.  \nLet $ n = 3^k $.  \nLet $ A = (a_0, a_1, \\dots, a_{n-1}) $, $ B = (b_0, b_1, \\dots, b_{n-1}) $ be sequences of non-negative integers.  \nFor $ x \\in \\{0, 1, \\dots, n-1\\} $, let $ x_i \\in \\{0,1,2\\} $ denote the $ i $-th ternary digit of $ x $, i.e., $ x = \\sum_{i=0}^{k-1} x_i \\cdot 3^i $.  \n\nDefine the tritwise mex function:  \n$$\n\\mathrm{mex}_3(i, j) = \\sum_{t=0}^{k-1} \\mathrm{mex}(i_t, j_t) \\cdot 3^t,\n$$  \nwhere $ \\mathrm{mex}(a, b) = \\min(\\{0,1,2\\} \\setminus \\{a, b\\}) $ for $ a, b \\in \\{0,1,2\\} $.  \n\n**Constraints**  \n1. $ 1 \\leq k \\leq 12 $  \n2. $ 0 \\leq a_i \\leq 10^3 $ for all $ i \\in \\{0, \\dots, n-1\\} $  \n3. $ 0 \\leq b_i \\leq 10^3 $ for all $ i \\in \\{0, \\dots, n-1\\} $  \n\n**Objective**  \nCompute the sequence $ C = (c_0, c_1, \\dots, c_{n-1}) $, where:  \n$$\nc_k = \\sum_{\\substack{0 \\leq i, j < n \\\\ \\mathrm{mex}_3(i,j) = k}} a_i \\cdot b_j\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10212A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}