# C. Cake Assignment [문제 링크](https://codeforces.com/contest/2139/problem/C) ## Problem Statement 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$. ## Input 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. ## Output 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 = 1$ or $o_i = 2$), where $o_i = 1$ means that in the $i$-th step, Chocola gave half of her cakes to Vanilla (operation 1), and $o_i = 2$ means that Vanilla gave half of her cakes to Chocola (operation 2). ## 풀이 x부터 $2^k$까지 반대로 만들어나가면 된다. 둘 중 작은 수가 이전에 전달해준 수이기 때문에 어떤 수가 작은지 확인하여 그 수만큼 변경시키며 연산 과정을 찾는다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { ll k, x; cin >> k >> x; ll total = 1LL<<k+1; ll a = 1LL<<k; vector<ll> res; while(a!=x) { if(x<total-x) { x<<=1; res.push_back(1); } else { x -= (total-x); res.push_back(2); } } cout << res.size() << '\n'; for(int i=res.size()-1;i>=0;i--) cout << res[i] << ' '; cout << '\n'; } } ```