2138A.md (2969B)
1 Source: https://codeforces.com/problemset/problem/2138/A 2 3 A. Cake Assignment 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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. 24 25 In one step, they can perform exactly one of the following two operations: 26 27 1. Chocola gives half of her cakes to Vanilla. This operation is only allowed if Chocola currently has an even number of cakes. 28 2. Vanilla gives half of her cakes to Chocola. This operation is only allowed if Vanilla currently has an even number of cakes. 29 30 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. 31 32 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$. 33 34 Input 35 36 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. 37 38 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. 39 40 Output 41 42 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. 43 44 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). 45 46 Example 47 48 Input 49 50 ``` 51 4 52 53 2 3 54 55 2 4 56 57 3 7 58 59 2 5 60 ``` 61 62 Output 63 64 ``` 65 2 66 2 1 67 0 68 69 3 70 2 2 1 71 2 72 1 2 73 ``` 74 75 Note 76 77 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. 78 79 $$\{4, 4\} \xrightarrow{o_1 = \mathtt{2}} \{6, 2\} \xrightarrow{o_2 = \mathtt{1}} \{3, 5\}$$ 80 81 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. 82 83 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. 84 85 $$\{8, 8\} \xrightarrow{o_1 = \mathtt{2}} \{12, 4\} \xrightarrow{o_2 = \mathtt{2}} \{14, 2\} \xrightarrow{o_3 = \mathtt{1}} \{7, 9\}$$