Code shoe set - mt3114 · interesting balance - explain it with examples

---

Interesting balance

• Interesting balance .

The time limit ：1 second
Space restriction ：64M

---

Title Description

Small brother likes balance very much , One day, brother Xiaoma received a seesaw from a friend , When the weight of both sides of the seesaw is the same, it reaches balance . Just right , He has some weights $2^0,2^1\cdots ,2^{\infty }$, There is only one weight of each kind , Brother Xiaoma hopes to put some weights on both sides , So that the absolute value of the weight difference between the two sides is $x$, Weights must be placed on both sides , You can't let go of weights , Can you do it for me , Give your method .

---

Input description

Enter an integer $x(1\le x<2^{30})$

---

Output description

Output four lines

The first line represents the number of French yards on the left

The second row lists the weight of the weight that represents the left weight

A number in the third line represents the number of weights on the right

The fourth row lists the weight of the weight placed by the weight on the right

Each line of numbers is separated by a space

 remarks ：
 Any method to satisfy the meaning of the question is legal 

---

Example 1

Input

6

Output

1 
2
1 
8

Topic analysis

In fact, we can count $x$ In binary terms .

For example, in the example $6=110_{(2)}$

Then we calculate $x$ How many bits are there in the binary of

Examples $6$ Binary system $110$ Yes $3$ position

Then we put a weight of... On one side of the balance $2^{positionCount}$ The weight of

Examples $6$ The weight placed on one side of is $2^3=8$ The weight of

Then we calculate the weight of the weight that needs to be placed on the other side （ Write it down as $remain$）$remain=2^{positionCount}-x$

Examples $6$ Put the weight on the other side of the $remain$ by $8-6=2$

Finally, put $remain$ Written in binary form , The first $i$ Position as $1$ If so, put a weight of $2^i$ The weight of （ From $0$ From the beginning ）

Examples $6$ The other side $2=10_{(2)}$, The first $0$ Is it $0$, The first $1$ Is it $1$, So put a weight of $2^1=2$ The weight of .

Here we are , Problem solving .

AC Code

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int main() {
    
    int n;
    cin >> n;
    int k = 1;
    while (k <= n) {
    
        k *= 2;
    }
    int remain = k - n;
    cout << 1 << endl;
    cout << k << endl;
    vector<int> right;
    int k2 = 1;
    while (k2 < k) {
    
        if (k2 & remain) {
    
            right.push_back(k2);
        }
        k2 *= 2;
    }
    cout << right.size() << endl;
    for (int i = 0; i < right.size(); i++) {
    
        cout << right[i] << ' ';
    }
    puts("");
    return 0;
}

Update the weekly competition solution of elite class in advance every week , Focus , Neverlost

Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125545873