## 1. Abridged problem statement

You are given `n` coins, exactly one of which is fake. The fake coin has a different weight, but you do not know whether it is lighter or heavier.

Using a balance scale, output an optimal decision script that always determines the fake coin using the minimum possible number of weighings in the worst case.

For each weighing, both pans must contain the same number of coins, and a coin cannot appear on both pans. The script must only include possible outcome branches.

Input: one integer `n`, `3 ≤ n ≤ 100`.

Output: a script beginning with

```text
need X weighings
```

where `X` is the minimum possible worst-case number of weighings, followed by the decision tree.

---

## 2. Detailed editorial

This is a classic fake coin balance puzzle.

The important twist is that we only need to identify **which coin** is fake. We do **not** need to determine whether it is lighter or heavier.

The optimal number of weighings is

```text
minimum w such that (3^w - 1) / 2 >= n
```

The provided solution constructs an actual optimal decision tree.

---

### Types of subproblems

The algorithm maintains two kinds of states.

---

### 1. Unknown-direction state

We have a set of suspect coins, and for each suspect coin we do not know whether it is lighter or heavier.

Additionally, we may have some known genuine coins.

This state is represented by:

```cpp
build_unknown(suspects, known_good)
```

---

### 2. Signed state

We have two suspect groups:

- `light`: coins that, if fake, must be lighter.
- `heavy`: coins that, if fake, must be heavier.

This state is represented by:

```cpp
build_signed(light, heavy, known_good)
```

Once the fake coin’s possible direction is known, each weighing can split the possibilities into roughly three equal groups, because the balance has three outcomes:

```text
<
=
>
```

So a signed state with `T` candidates can be solved in about `ceil(log_3 T)` weighings.

---

## Unknown state without known-good coins

This is the initial situation.

Suppose we have `sz` suspects and no known genuine coin.

We choose the smallest `k` such that:

```text
(3^k - 1) / 2 >= sz
```

Then we put `a` suspects on the left pan and `a` suspects on the right pan, where approximately:

```text
a = (3^(k-1) - 1) / 2
```

The remaining suspects are left off the scale.

Example structure:

```text
weigh A vs B
```

Possible outcomes:

### Left pan lighter

Then the fake coin is either:

- in `A` and lighter, or
- in `B` and heavier.

This becomes a signed state:

```cpp
build_signed(A, B, off)
```

The off-scale coins are genuine, because an imbalance occurred.

### Left pan heavier

Symmetric case:

- coins in `B` may be lighter,
- coins in `A` may be heavier.

### Balance

Then all coins on the scale are genuine, and the fake coin is among the off-scale coins.

So we recurse:

```cpp
build_unknown(off, newly_known_good)
```

---

## Unknown state with known-good coins

If we already have genuine coins, the problem is easier.

We can weigh suspects directly against genuine coins:

```text
weigh suspects vs known_good
```

If the suspect side is lighter, then the fake is among those suspects and is lighter.

If the suspect side is heavier, then the fake is among those suspects and is heavier.

If the scale balances, those suspects are genuine and the fake is among the remaining suspects.

The known-good unknown state has capacity:

```text
(3^k + 1) / 2
```

with `k` remaining weighings.

---

## Signed state splitting

Suppose we have:

```text
L = number of light-suspects
H = number of heavy-suspects
T = L + H
```

We want to divide the possibilities into three groups of roughly equal size.

The solution chooses:

```cpp
s = (T + 1) / 3
```

Then it places `s` possible cases on the left pan and `s` possible cases on the right pan, carefully mixing light-suspects and heavy-suspects.

The key observation:

- If a heavy suspect is on the left pan and the left pan is heavier, that suspect remains possible.
- If a light suspect is on the right pan and the left pan is heavier, that suspect remains possible.
- If the scale balances, all weighed suspects are eliminated, and the fake is among the off-scale suspects.

So each outcome produces another smaller signed state.

---

## Base cases

### One suspect

If only one suspect remains, it must be fake:

```text
fake x
```

### Two suspects, same direction

For example, both are heavy-suspects.

Weigh them against each other:

```text
weigh a vs b
```

If left is heavier, `a` is fake.  
If left is lighter, `b` is fake.

For two light-suspects, the interpretation is reversed.

### Two suspects, one light and one heavy

Use a known genuine coin.

Example:

```text
weigh light_suspect vs known_good
```

If it is lighter, the light-suspect is fake.  
If it balances, the heavy-suspect is fake.

---

## Correctness argument

The algorithm is correct because every recursive branch preserves the exact set of possibilities consistent with the observed outcomes.

- In an unknown state, an imbalance determines the possible sign of the fake coin.
- In a balanced result, all weighed suspects are proven genuine.
- In a signed state, each outcome corresponds exactly to one subset of signed possibilities.

The recursion stops only when a single coin is forced to be fake.

The number of weighings is optimal because a balance weighing has three possible outcomes, and the classical optimal capacity for identifying one fake coin without knowing its direction is:

```text
(3^w - 1) / 2
```

The solution chooses the minimum `w` satisfying this bound and constructs a decision tree achieving it.

---

## 3. Provided C++ solution with detailed comments

```cpp
#include <bits/stdc++.h> // Includes almost all standard C++ headers.

using namespace std; // Allows using standard library names without std::.

// Output operator for pairs.
// Not essential to the core algorithm, but useful as a helper.
template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second; // Print pair as "first second".
}

// Input operator for pairs.
template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second; // Read pair elements.
}

// Input operator for vectors.
template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) { // Read every element of the vector.
        in >> x;
    }
    return in;
};

// Output operator for vectors.
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) { // Print every element of the vector.
        out << x << ' ';
    }
    return out;
};

int n; // Number of coins.

// Reads the input.
void read() {
    cin >> n;
}

// Prints one weighing instruction with indentation.
//
// Example:
//
//   weigh 1+2 vs 3+4
//
void do_print_weigh(const vector<int>& l, const vector<int>& r, int lev) {
    cout << string(lev * 2, ' ') << "weigh "; // Indentation and keyword.

    for(size_t i = 0; i < l.size(); i++) { // Print left pan coins.
        if(i > 0) {
            cout << "+"; // Coins are separated by plus signs.
        }
        cout << l[i];
    }

    cout << " vs "; // Separator between the two pans.

    for(size_t i = 0; i < r.size(); i++) { // Print right pan coins.
        if(i > 0) {
            cout << "+";
        }
        cout << r[i];
    }

    cout << "\n";
}

// This class represents one node of the decision tree.
class Solution {
  public:
    vector<int> lhs; // Coins on the left pan for this node's weighing.
    vector<int> rhs; // Coins on the right pan for this node's weighing.

    Solution* equal_branch;   // Child if the weighing balances.
    Solution* less_branch;    // Child if left pan is lighter.
    Solution* greater_branch; // Child if left pan is heavier.

    int fake_if_leaf; // If this is a leaf, stores the fake coin number.

    // Constructor for an internal weighing node.
    Solution(vector<int> _lhs, vector<int> _rhs) {
        lhs = _lhs; // Store left pan.
        rhs = _rhs; // Store right pan.

        equal_branch = nullptr;   // Initially no children.
        less_branch = nullptr;
        greater_branch = nullptr;

        fake_if_leaf = 0; // Zero means this is not a leaf.
    }

    // Constructor for a leaf node.
    Solution(int f) {
        fake_if_leaf = f; // Store the fake coin.

        equal_branch = nullptr; // Leaf has no children.
        less_branch = nullptr;
        greater_branch = nullptr;
    }

    // Builds a solution for an unknown-direction state.
    //
    // suspects:
    //   Coins that may be fake, direction unknown.
    //
    // known_good:
    //   Coins known to be genuine.
    static Solution* build_unknown(
        const vector<int>& suspects,
        const vector<int>& known_good
    );

    // Builds a solution for a signed state.
    //
    // light:
    //   Coins that, if fake, must be lighter.
    //
    // heavy:
    //   Coins that, if fake, must be heavier.
    //
    // known_good:
    //   Known genuine coins.
    static Solution* build_signed(
        const vector<int>& light,
        const vector<int>& heavy,
        const vector<int>& known_good
    );

    // Prints this decision tree recursively.
    void print(int lev) const {
        // If this is a leaf, print the answer.
        if(fake_if_leaf > 0) {
            cout << string(lev * 2, ' ') << "fake " << fake_if_leaf << "\n";
            return;
        }

        // Otherwise print this node's weighing.
        do_print_weigh(lhs, rhs, lev);

        // Print only possible branches.

        if(less_branch) {
            cout << string(lev * 2, ' ') << "case <:\n";
            less_branch->print(lev + 1);
        }

        if(equal_branch) {
            cout << string(lev * 2, ' ') << "case =:\n";
            equal_branch->print(lev + 1);
        }

        if(greater_branch) {
            cout << string(lev * 2, ' ') << "case >:\n";
            greater_branch->print(lev + 1);
        }

        // End this decision block.
        cout << string(lev * 2, ' ') << "end\n";
    }
};

// Computes 3^k.
int pow3(int k) {
    int p = 1;

    while(k--) {
        p *= 3;
    }

    return p;
}

// Builds a decision tree when suspects may be either lighter or heavier.
Solution* Solution::build_unknown(
    const vector<int>& suspects,
    const vector<int>& known_good
) {
    int sz = suspects.size(); // Number of unknown-direction suspects.

    // No suspects means no valid subtree.
    if(sz == 0) {
        return nullptr;
    }

    // If only one coin is possible, it is fake.
    if(sz == 1) {
        return new Solution(suspects[0]);
    }

    // Case 1: we have genuine coins available.
    if(!known_good.empty()) {
        int k = 0;

        // Find minimum k such that this many suspects can be handled
        // in an unknown state with known-good coins.
        while((pow3(k) + 1) / 2 < sz) {
            k++;
        }

        // We can compare up to 3^(k-1) suspects directly with good coins.
        int b = min(pow3(k - 1), sz);

        // These suspects are weighed.
        vector<int> weighed(suspects.begin(), suspects.begin() + b);

        // These suspects are left for the equal branch.
        vector<int> remaining(suspects.begin() + b, suspects.end());

        // Same number of known-good coins are placed on the opposite pan.
        vector<int> good_on_scale(known_good.begin(), known_good.begin() + b);

        // Weigh suspects against known genuine coins.
        Solution* node = new Solution(weighed, good_on_scale);

        // If suspect side is lighter, fake is among weighed suspects
        // and must be lighter.
        node->less_branch = build_signed(weighed, {}, known_good);

        // If suspect side is heavier, fake is among weighed suspects
        // and must be heavier.
        node->greater_branch = build_signed({}, weighed, known_good);

        // If balance, weighed suspects are genuine, fake is among remaining.
        if(!remaining.empty()) {
            vector<int> new_good = known_good;

            // Add the weighed suspects to the known genuine set.
            new_good.insert(new_good.end(), weighed.begin(), weighed.end());

            node->equal_branch = build_unknown(remaining, new_good);
        }

        return node;
    }

    // Case 2: no known genuine coins.
    // This is the initial type of state.

    int k = 0;

    // Find minimum k such that (3^k - 1) / 2 can cover sz suspects.
    while((pow3(k) - 1) / 2 < sz) {
        k++;
    }

    // Number of coins to place on each pan.
    int a = (pow3(k - 1) - 1) / 2;

    // Ensure at least one coin is placed on each pan.
    a = max(a, 1);

    // Ensure at least one coin remains off-scale if possible.
    a = min(a, (sz - 1) / 2);

    // Left pan suspects.
    vector<int> left(suspects.begin(), suspects.begin() + a);

    // Right pan suspects.
    vector<int> right(suspects.begin() + a, suspects.begin() + 2 * a);

    // Off-scale suspects.
    vector<int> off(suspects.begin() + 2 * a, suspects.end());

    // Create weighing node.
    Solution* node = new Solution(left, right);

    // If the scale balances, all weighed coins become known genuine.
    vector<int> new_known;
    new_known.insert(new_known.end(), left.begin(), left.end());
    new_known.insert(new_known.end(), right.begin(), right.end());

    // If left is lighter:
    // - fake may be light among left,
    // - or heavy among right.
    // Off-scale coins are genuine in this branch.
    node->less_branch = build_signed(left, right, off);

    // If left is heavier:
    // - fake may be light among right,
    // - or heavy among left.
    node->greater_branch = build_signed(right, left, off);

    // If equal, fake is among off-scale coins.
    if(!off.empty()) {
        node->equal_branch = build_unknown(off, new_known);
    }

    return node;
}

// Builds a decision tree when every suspect has a known possible direction.
Solution* Solution::build_signed(
    const vector<int>& light,
    const vector<int>& heavy,
    const vector<int>& known_good
) {
    int L = light.size(); // Number of light-suspects.
    int H = heavy.size(); // Number of heavy-suspects.
    int tot = L + H;      // Total signed suspects.

    // No suspects: impossible branch.
    if(tot == 0) {
        return nullptr;
    }

    // Only one suspect: it must be fake.
    if(tot == 1) {
        return new Solution(light.empty() ? heavy[0] : light[0]);
    }

    // Special handling for two suspects.
    if(tot == 2) {
        // Both suspects are heavy-suspects.
        if(L == 0) {
            Solution* node = new Solution({heavy[0]}, {heavy[1]});

            // If left pan is lighter, right heavy-suspect is fake.
            node->less_branch = new Solution(heavy[1]);

            // If left pan is heavier, left heavy-suspect is fake.
            node->greater_branch = new Solution(heavy[0]);

            return node;
        }

        // Both suspects are light-suspects.
        else if(H == 0) {
            Solution* node = new Solution({light[0]}, {light[1]});

            // If left pan is lighter, left light-suspect is fake.
            node->less_branch = new Solution(light[0]);

            // If left pan is heavier, right light-suspect is fake.
            node->greater_branch = new Solution(light[1]);

            return node;
        }

        // One light-suspect and one heavy-suspect.
        // Use a known genuine coin as reference.
        else {
            Solution* node = new Solution({light[0]}, {known_good[0]});

            // If the light-suspect is lighter than genuine, it is fake.
            node->less_branch = new Solution(light[0]);

            // If it balances, then the heavy-suspect must be fake.
            node->equal_branch = new Solution(heavy[0]);

            return node;
        }
    }

    // General signed case.
    // We want to split the possibilities into three roughly equal parts.

    int s = (tot + 1) / 3; // Target size for < and > branches.

    // Choose how many heavy suspects to put on each pan.
    int h = min(s, H / 2);

    // Remaining slots are filled with light suspects.
    int l = s - h;

    // If there are not enough light suspects for both pans,
    // reduce l and increase h.
    if(2 * l > L) {
        l = L / 2;
        h = s - l;
    }

    vector<int> lp, rp; // Left pan and right pan.

    // Put h heavy-suspects on the left pan.
    for(int i = 0; i < h; i++) {
        lp.push_back(heavy[i]);
    }

    // Put l light-suspects on the left pan.
    for(int i = 0; i < l; i++) {
        lp.push_back(light[i]);
    }

    // Put h heavy-suspects on the right pan.
    for(int i = h; i < 2 * h; i++) {
        rp.push_back(heavy[i]);
    }

    // Put l light-suspects on the right pan.
    for(int i = l; i < 2 * l; i++) {
        rp.push_back(light[i]);
    }

    // If left pan is heavier:
    // possible suspects are:
    // - heavy suspects on the left,
    // - light suspects on the right.
    vector<int> gt_heavy(heavy.begin(), heavy.begin() + h);
    vector<int> gt_light(light.begin() + l, light.begin() + 2 * l);

    // If balanced:
    // all weighed suspects are genuine,
    // so only off-scale signed suspects remain.
    vector<int> eq_light(light.begin() + 2 * l, light.end());
    vector<int> eq_heavy(heavy.begin() + 2 * h, heavy.end());

    // If left pan is lighter:
    // possible suspects are:
    // - light suspects on the left,
    // - heavy suspects on the right.
    vector<int> lt_light(light.begin(), light.begin() + l);
    vector<int> lt_heavy(heavy.begin() + h, heavy.begin() + 2 * h);

    // Create this weighing node.
    Solution* node = new Solution(lp, rp);

    // Recurse on each possible outcome.
    node->less_branch = build_signed(lt_light, lt_heavy, known_good);
    node->equal_branch = build_signed(eq_light, eq_heavy, known_good);
    node->greater_branch = build_signed(gt_light, gt_heavy, known_good);

    return node;
}

// Solves the problem.
void solve() {
    // Create coin list: 1, 2, ..., n.
    vector<int> coins(n);
    iota(coins.begin(), coins.end(), 1);

    int w = 0;

    // Compute minimum w such that (3^w - 1) / 2 >= n.
    while((pow3(w) - 1) / 2 < n) {
        w++;
    }

    // Print optimal worst-case number of weighings.
    cout << "need " << w << " weighings\n";

    // Build the decision tree from the initial unknown state.
    Solution* root = Solution::build_unknown(coins, {});

    // Print the decision tree.
    root->print(0);
}

int main() {
    ios_base::sync_with_stdio(false); // Fast IO.
    cin.tie(nullptr);                 // Untie cin from cout.

    int T = 1; // Only one test case.

    // Process the single test case.
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python solution with detailed comments

```python
import sys


def pow3(k):
    """Return 3^k."""
    result = 1

    for _ in range(k):
        result *= 3

    return result


def format_side(coins):
    """Format one pan of the balance, e.g. [1, 2, 3] -> '1+2+3'."""
    return "+".join(map(str, coins))


class Node:
    """
    A node in the decision tree.

    A node is either:
    - a leaf, storing the fake coin, or
    - an internal node, storing one weighing and its branches.
    """

    def __init__(self, lhs=None, rhs=None, fake=None):
        # Coins on left pan.
        self.lhs = lhs

        # Coins on right pan.
        self.rhs = rhs

        # Fake coin number if this is a leaf.
        self.fake = fake

        # Branch for left pan lighter.
        self.less = None

        # Branch for balance.
        self.equal = None

        # Branch for left pan heavier.
        self.greater = None

    def print_tree(self, level, out):
        """Recursively print the decision tree."""

        indent = "  " * level

        # Leaf node: print answer.
        if self.fake is not None:
            out.append(f"{indent}fake {self.fake}")
            return

        # Internal node: print weighing.
        out.append(
            f"{indent}weigh {format_side(self.lhs)} vs {format_side(self.rhs)}"
        )

        # Print only possible branches.

        if self.less is not None:
            out.append(f"{indent}case <:")
            self.less.print_tree(level + 1, out)

        if self.equal is not None:
            out.append(f"{indent}case =:")
            self.equal.print_tree(level + 1, out)

        if self.greater is not None:
            out.append(f"{indent}case >:")
            self.greater.print_tree(level + 1, out)

        out.append(f"{indent}end")


def build_unknown(suspects, known_good):
    """
    Build a decision tree for an unknown-direction state.

    suspects:
        Coins that may be fake, with unknown direction.

    known_good:
        Coins known to be genuine.
    """

    sz = len(suspects)

    # No suspects means this branch is impossible.
    if sz == 0:
        return None

    # One suspect means that coin must be fake.
    if sz == 1:
        return Node(fake=suspects[0])

    # If we have known genuine coins, compare suspects against them.
    if known_good:
        k = 0

        # Capacity of an unknown-direction state with genuine references:
        # (3^k + 1) / 2
        while (pow3(k) + 1) // 2 < sz:
            k += 1

        # Number of suspects to weigh against genuine coins.
        b = min(pow3(k - 1), sz)

        # Suspects placed on the scale.
        weighed = suspects[:b]

        # Suspects left off the scale.
        remaining = suspects[b:]

        # Genuine coins used as references.
        good_on_scale = known_good[:b]

        # Create weighing node.
        node = Node(weighed, good_on_scale)

        # If suspect side is lighter, fake is among weighed suspects,
        # and it is lighter.
        node.less = build_signed(weighed, [], known_good)

        # If suspect side is heavier, fake is among weighed suspects,
        # and it is heavier.
        node.greater = build_signed([], weighed, known_good)

        # If balance, weighed suspects are genuine.
        if remaining:
            new_good = known_good + weighed
            node.equal = build_unknown(remaining, new_good)

        return node

    # Otherwise, this is an unknown state with no known genuine coins.

    k = 0

    # Initial-state capacity:
    # (3^k - 1) / 2
    while (pow3(k) - 1) // 2 < sz:
        k += 1

    # Number of suspects on each pan.
    a = (pow3(k - 1) - 1) // 2

    # Ensure the first weighing is meaningful.
    a = max(a, 1)

    # Leave at least one coin off-scale when possible.
    a = min(a, (sz - 1) // 2)

    # Split suspects into left pan, right pan, and off-scale.
    left = suspects[:a]
    right = suspects[a:2 * a]
    off = suspects[2 * a:]

    # Create weighing node.
    node = Node(left, right)

    # If left pan is lighter:
    # - fake may be a light coin on the left,
    # - or a heavy coin on the right.
    node.less = build_signed(left, right, off)

    # If left pan is heavier:
    # - fake may be a light coin on the right,
    # - or a heavy coin on the left.
    node.greater = build_signed(right, left, off)

    # If equal, the fake coin is among the off-scale coins,
    # and all weighed coins are known genuine.
    if off:
        new_good = left + right
        node.equal = build_unknown(off, new_good)

    return node


def build_signed(light, heavy, known_good):
    """
    Build a decision tree for a signed state.

    light:
        Coins that, if fake, must be lighter.

    heavy:
        Coins that, if fake, must be heavier.

    known_good:
        Known genuine coins.
    """

    L = len(light)
    H = len(heavy)
    total = L + H

    # Impossible branch.
    if total == 0:
        return None

    # Only one possible coin remains.
    if total == 1:
        if light:
            return Node(fake=light[0])
        else:
            return Node(fake=heavy[0])

    # Special case: two suspects.
    if total == 2:
        # Both suspects are heavy.
        if L == 0:
            node = Node([heavy[0]], [heavy[1]])

            # If left is lighter, right heavy-suspect is fake.
            node.less = Node(fake=heavy[1])

            # If left is heavier, left heavy-suspect is fake.
            node.greater = Node(fake=heavy[0])

            return node

        # Both suspects are light.
        elif H == 0:
            node = Node([light[0]], [light[1]])

            # If left is lighter, left light-suspect is fake.
            node.less = Node(fake=light[0])

            # If left is heavier, right light-suspect is fake.
            node.greater = Node(fake=light[1])

            return node

        # One light-suspect and one heavy-suspect.
        else:
            # Use a known genuine coin as reference.
            node = Node([light[0]], [known_good[0]])

            # If light-suspect is lighter than genuine, it is fake.
            node.less = Node(fake=light[0])

            # If they balance, the heavy-suspect must be fake.
            node.equal = Node(fake=heavy[0])

            return node

    # General signed case.

    # Target size for < and > branches.
    s = (total + 1) // 3

    # Try to use as many heavy suspects as possible on both pans.
    h = min(s, H // 2)

    # Fill remaining slots with light suspects.
    l = s - h

    # If not enough light suspects are available for both pans,
    # reduce light count and increase heavy count.
    if 2 * l > L:
        l = L // 2
        h = s - l

    # Left and right pans.
    left_pan = []
    right_pan = []

    # Put h heavy-suspects on the left pan.
    left_pan.extend(heavy[:h])

    # Put l light-suspects on the left pan.
    left_pan.extend(light[:l])

    # Put h heavy-suspects on the right pan.
    right_pan.extend(heavy[h:2 * h])

    # Put l light-suspects on the right pan.
    right_pan.extend(light[l:2 * l])

    # If left pan is heavier:
    # possible suspects are heavy suspects on left and light suspects on right.
    gt_heavy = heavy[:h]
    gt_light = light[l:2 * l]

    # If balance:
    # possible suspects are off-scale signed suspects.
    eq_light = light[2 * l:]
    eq_heavy = heavy[2 * h:]

    # If left pan is lighter:
    # possible suspects are light suspects on left and heavy suspects on right.
    lt_light = light[:l]
    lt_heavy = heavy[h:2 * h]

    # Create weighing node.
    node = Node(left_pan, right_pan)

    # Recurse on the three possible outcomes.
    node.less = build_signed(lt_light, lt_heavy, known_good)
    node.equal = build_signed(eq_light, eq_heavy, known_good)
    node.greater = build_signed(gt_light, gt_heavy, known_good)

    return node


def main():
    # Read n.
    data = sys.stdin.read().strip().split()
    n = int(data[0])

    # Coins are numbered from 1 to n.
    coins = list(range(1, n + 1))

    # Compute optimal number of weighings.
    w = 0
    while (pow3(w) - 1) // 2 < n:
        w += 1

    # Build output.
    out = []

    # First line.
    out.append(f"need {w} weighings")

    # Build and print the decision tree.
    root = build_unknown(coins, [])
    root.print_tree(0, out)

    # Write final answer.
    sys.stdout.write("\n".join(out))


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

---

## 5. Compressed editorial

Use two recursive states.

1. `unknown(suspects, good)`  
   Suspects may be lighter or heavier.

2. `signed(light, heavy, good)`  
   A coin in `light`, if fake, is known to be lighter.  
   A coin in `heavy`, if fake, is known to be heavier.

The optimal number of weighings is the smallest `w` such that:

```text
(3^w - 1) / 2 >= n
```

In an initial unknown state without known-good coins, weigh `a` suspects against `a` other suspects. If the scale tilts, the problem becomes signed. If it balances, the weighed coins become known genuine.

In an unknown state with known-good coins, weigh suspects directly against genuine coins. An imbalance determines the fake’s direction; balance eliminates those suspects.

In a signed state, split the signed possibilities into three nearly equal groups corresponding to outcomes `<`, `=`, and `>`. Recurse on the matching group.

Base cases handle one or two suspects directly.

This constructs a valid decision tree whose depth equals the optimal lower bound, so the output uses the minimum possible number of weighings.