CF2138A Cake Assignment

Chocola and Vanilla love cakes. Today, the manager of a cake shop gave them a total of $$$2^{k+1}$$$ cakes. The cakes were distributed evenly, so each of them initially received $$$2^k$$$ cakes. However, Chocola and Vanilla now want to redistribute the cakes such that Chocola ends up with exactly $$$x$$$ cakes and Vanilla gets the remaining $$$2^{k+1}-x$$$ cakes. In one step, they can perform exactly one of the following two operations: 1. Chocola gives half of her cakes to Vanilla. This operation is only allowed if Chocola currently has an even number of cakes. 2. Vanilla gives half of her cakes to Chocola. This operation is only allowed if Vanilla currently has an even number of cakes. Your task is to determine the minimum number of steps required to reach the target distribution and to output any valid sequence of operations achieving that minimum. It can be proven that, under the given constraints, a valid solution always exists, and the minimum number of steps required is at most $$$120$$$.

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \\le t \\le 1000$$$). The description of the test cases follows. The first line of each test case contains two integers $$$k$$$ and $$$x$$$ ($$$1 \\le k \\le 60$$$, $$$1 \\le x \\le 2^{k+1}-1$$$) — each person initially received $$$2^k$$$ cakes, and $$$x$$$ is the number of cakes Chocola should have after redistribution.

For each test case, output a single integer $$$n$$$ ($$$0\\le n\\le 120$$$) representing the minimum number of steps required for them to redistribute the cakes accordingly. On the next line, output $$$n$$$ integers $$$o\_1, o\_2, \\ldots, o\_n$$$ ($$$o\_i = \\mathtt{1}$$$ or $$$o\_i = \\mathtt{2}$$$), where $$$o\_i = \\mathtt{1}$$$ means that in the $$$i$$$-th step, Chocola gave half of her cakes to Vanilla (operation 1), and $$$o\_i = \\mathtt{2}$$$ means that Vanilla gave half of her cakes to Chocola (operation 2).

In the first test case, they can use the following steps so that Chocola has exactly $$$x = 3$$$ cakes and Vanilla has exactly $$$2 ^ {k + 1} - x = 5$$$ cakes. We use $$$\\{a, b\\}$$$ to denote that Chocola currently has $$$a$$$ cakes and Vanilla currently has $$$b$$$ cakes. $$$$$$\\{4, 4\\} \\xrightarrow{o\_1 = \\mathtt{2}} \\{6, 2\\} \\xrightarrow{o\_2 = \\mathtt{1}} \\{3, 5\\}$$$$$$ In the second test case, Chocola already has exactly $$$x = 4$$$ cakes and Vanilla already has exactly $$$2 ^ {k + 1} - x = 4$$$ cakes, so no operations are required. In the third test case, they can use the following steps so that Chocola has exactly $$$x = 7$$$ cakes and Vanilla has exactly $$$2 ^ {k + 1} - x = 9$$$ cakes. $$$$$$\\{8, 8\\} \\xrightarrow{o\_1 = \\mathtt{2}} \\{12, 4\\} \\xrightarrow{o\_2 = \\mathtt{2}} \\{14, 2\\} \\xrightarrow{o\_3 = \\mathtt{1}} \\{7, 9\\}$$$$$$