## 1) Abridged problem statement

Given a starting voltage of 1 and two amplifier types:
- Type 1: X -> 2·X - 1
- Type 2: X -> 2·X + 1

you need to reach exactly N volts (1 ≤ N ≤ 2·10⁹) using the fewest amplifiers. Output the minimum number of amplifiers and a sequence (1s and 2s) describing the types in order. If it's impossible, print "No solution."

---

## 2) Detailed editorial

Goal: build N from 1 with operations X -> 2X-1 or X -> 2X+1. Observe:
- Starting from 1, every result is odd. Thus N must be odd; if N is even, no solution.
- Brute-force BFS over all reachable voltages is infeasible (N up to 2·10⁹).

Idea: work backwards from N to 1 by inverting operations:
- Inverse of X->2X-1 is N->(N+1)/2, corresponding to a type-1 amplifier just before N.
- Inverse of X->2X+1 is N->(N-1)/2, corresponding to a type-2 amplifier.

Since N is odd, both (N±1)/2 are integers. We need the shortest reverse path to 1. A greedy rule works in O(log N) steps:
1. While N>1, compute x=(N-1)/2 and y=(N+1)/2.
2. Exactly one of x, y is odd (the other even). To stay odd in the next step, pick the even predecessor's opposite — i.e., pick the odd one:
   - If x is even (meaning y is odd), record "1" and set N <- y.
   - If x is odd, record "2" and set N <- x.
3. Repeat until N=1.
4. Reverse the recorded operations: this is the forward sequence from 1 to the original N.

Correctness: always keeps the chain valid (next reverse step has an odd N), and it yields the minimal number of steps because any deviation would force an even intermediate and dead-end.
Complexity: each step halves N roughly, so O(log N) time and memory.

---

## 3) C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;

void read() { cin >> n; }

void solve() {
    // Work backwards from the target N to the outlet value 1. A type-1
    // amplifier maps X -> 2X-1 and a type-2 amplifier maps X -> 2X+1, so any
    // reachable value is odd; even N has no solution. Inverting, the previous
    // value before reaching n is either (n+1)/2 (undoing type-1) or (n-1)/2
    // (undoing type-2). Both candidates differ by one and exactly one of them
    // is even; the even predecessor is a dead end because from an even value no
    // amplifier can have produced it except trivially, so we are forced to pick
    // the odd predecessor each step, giving a unique greedy chain.
    //
    // Record which amplifier type was undone at each step, then reverse to get
    // the sequence from the outlet to the machine.

    if(n % 2 == 0) {
        cout << "No solution\n";
        return;
    }

    vector<int> ans;
    while(n > 1) {
        int x = (n - 1) / 2;
        int y = (n + 1) / 2;
        if(x % 2 == 0) {
            ans.push_back(1);
            n = y;
        } else {
            ans.push_back(2);
            n = x;
        }
    }

    reverse(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 4) Python Solution

```python
import sys

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])

    # If n is even, no sequence of 2X±1 from 1 can reach it
    if n % 2 == 0:
        print("No solution")
        return

    ops = []  # will store reverse operations
    while n > 1:
        # Compute both possible predecessors
        a = (n - 1) // 2  # from a with type-2 forward gives n = 2a+1
        b = (n + 1) // 2  # from b with type-1 forward gives n = 2b-1

        # Choose the one that remains odd (so next iteration is valid)
        if a % 2 == 1:
            ops.append(2)
            n = a
        else:
            ops.append(1)
            n = b

    # We built ops from target back to 1; reverse to get forward sequence
    ops.reverse()

    # Output result
    print(len(ops))
    if ops:
        print(" ".join(map(str, ops)))

if __name__ == "__main__":
    main()
```

---

## 5) Compressed editorial

Only odd targets are reachable because every operation yields an odd. Reverse greedily: from N repeatedly pick the inverse that produces an odd predecessor—(N-1)/2 if it's odd implies forward type 2, otherwise (N+1)/2 implies type 1—until reaching 1. Reverse that list for the forward amplifier sequence. This takes O(log N) time and is optimal.
