## 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. 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 do_print_weigh(const vector<int>& l, const vector<int>& r, int lev) {
    cout << string(lev * 2, ' ') << "weigh ";
    for(size_t i = 0; i < l.size(); i++) {
        if(i > 0) {
            cout << "+";
        }
        cout << l[i];
    }
    cout << " vs ";
    for(size_t i = 0; i < r.size(); i++) {
        if(i > 0) {
            cout << "+";
        }
        cout << r[i];
    }
    cout << "\n";
}

class Solution {
  public:
    vector<int> lhs;
    vector<int> rhs;
    Solution* equal_branch;
    Solution* less_branch;
    Solution* greater_branch;
    int fake_if_leaf;

    Solution(vector<int> _lhs, vector<int> _rhs) {
        lhs = _lhs;
        rhs = _rhs;
        equal_branch = nullptr;
        less_branch = nullptr;
        greater_branch = nullptr;
        fake_if_leaf = 0;
    }

    Solution(int f) {
        fake_if_leaf = f;
        equal_branch = nullptr;
        less_branch = nullptr;
        greater_branch = nullptr;
    }

    static Solution* build_unknown(
        const vector<int>& suspects, const vector<int>& known_good
    );

    static Solution* build_signed(
        const vector<int>& light, const vector<int>& heavy,
        const vector<int>& known_good
    );

    void print(int lev) const {
        if(fake_if_leaf > 0) {
            cout << string(lev * 2, ' ') << "fake " << fake_if_leaf << "\n";
            return;
        }
        do_print_weigh(lhs, rhs, lev);
        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);
        }
        cout << string(lev * 2, ' ') << "end\n";
    }
};

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

    return p;
}

Solution* Solution::build_unknown(
    const vector<int>& suspects, const vector<int>& known_good
) {
    int sz = suspects.size();
    if(sz == 0) {
        return nullptr;
    }
    if(sz == 1) {
        return new Solution(suspects[0]);
    }

    if(!known_good.empty()) {
        int k = 0;
        while((pow3(k) + 1) / 2 < sz) {
            k++;
        }
        int b = min(pow3(k - 1), sz);

        vector<int> weighed(suspects.begin(), suspects.begin() + b);
        vector<int> remaining(suspects.begin() + b, suspects.end());
        vector<int> good_on_scale(known_good.begin(), known_good.begin() + b);

        Solution* node = new Solution(weighed, good_on_scale);
        node->less_branch = build_signed(weighed, {}, known_good);
        node->greater_branch = build_signed({}, weighed, known_good);
        if(!remaining.empty()) {
            vector<int> new_good = known_good;
            new_good.insert(new_good.end(), weighed.begin(), weighed.end());
            node->equal_branch = build_unknown(remaining, new_good);
        }
        return node;
    }

    int k = 0;
    while((pow3(k) - 1) / 2 < sz) {
        k++;
    }
    int a = (pow3(k - 1) - 1) / 2;
    a = max(a, 1);
    a = min(a, (sz - 1) / 2);

    vector<int> left(suspects.begin(), suspects.begin() + a);
    vector<int> right(suspects.begin() + a, suspects.begin() + 2 * a);
    vector<int> off(suspects.begin() + 2 * a, suspects.end());

    Solution* node = new Solution(left, right);
    vector<int> new_known;
    new_known.insert(new_known.end(), left.begin(), left.end());
    new_known.insert(new_known.end(), right.begin(), right.end());

    node->less_branch = build_signed(left, right, off);
    node->greater_branch = build_signed(right, left, off);
    if(!off.empty()) {
        node->equal_branch = build_unknown(off, new_known);
    }
    return node;
}

Solution* Solution::build_signed(
    const vector<int>& light, const vector<int>& heavy,
    const vector<int>& known_good
) {
    int L = light.size(), H = heavy.size();
    int tot = L + H;
    if(tot == 0) {
        return nullptr;
    }
    if(tot == 1) {
        return new Solution(light.empty() ? heavy[0] : light[0]);
    }
    if(tot == 2) {
        if(L == 0) {
            Solution* node = new Solution({heavy[0]}, {heavy[1]});
            node->less_branch = new Solution(heavy[1]);
            node->greater_branch = new Solution(heavy[0]);
            return node;
        } else if(H == 0) {
            Solution* node = new Solution({light[0]}, {light[1]});
            node->less_branch = new Solution(light[0]);
            node->greater_branch = new Solution(light[1]);
            return node;
        } else {
            Solution* node = new Solution({light[0]}, {known_good[0]});
            node->less_branch = new Solution(light[0]);
            node->equal_branch = new Solution(heavy[0]);
            return node;
        }
    }

    int s = (tot + 1) / 3;
    int h = min(s, H / 2);
    int l = s - h;
    if(2 * l > L) {
        l = L / 2;
        h = s - l;
    }

    vector<int> lp, rp;
    for(int i = 0; i < h; i++) {
        lp.push_back(heavy[i]);
    }
    for(int i = 0; i < l; i++) {
        lp.push_back(light[i]);
    }
    for(int i = h; i < 2 * h; i++) {
        rp.push_back(heavy[i]);
    }
    for(int i = l; i < 2 * l; i++) {
        rp.push_back(light[i]);
    }

    vector<int> gt_heavy(heavy.begin(), heavy.begin() + h);
    vector<int> gt_light(light.begin() + l, light.begin() + 2 * l);

    vector<int> eq_light(light.begin() + 2 * l, light.end());
    vector<int> eq_heavy(heavy.begin() + 2 * h, heavy.end());

    vector<int> lt_light(light.begin(), light.begin() + l);
    vector<int> lt_heavy(heavy.begin() + h, heavy.begin() + 2 * h);

    Solution* node = new Solution(lp, rp);
    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;
}

void solve() {
    // Nowadays, this is a fairly popular setting, although there are different
    // variants. It's commonly known as the balance puzzle. Naive idea is that
    // you would need log2(n) comparisons, but if you compare two halves as a
    // start and know if the outlier is heavier / lighter, you can instead split
    // into 3 groups, compare two of them, and depending on whether they are <,
    // =, or >, go to the corresponding part. This gives us a log3(n), but we
    // need to first know if we have something heavier or lighter.
    //
    // The optimal strategy uses ceil(log3(2n+1)) weightings and maintains two
    // kinds of sub-problems: unknown (suspects whose direction is unknown,
    // plus known-good coins) and signed (light-suspects + heavy-suspects +
    // known-good coins).
    //
    // For the unknown state without good coins (the initial call), we weigh
    // a = (3^(k-1) - 1) / 2 suspects against a other suspects, leaving at
    // least one off the scale (to serve as a known-good reference later).
    // Imbalance yields a signed sub-problem of size 2a; balance yields an
    // unknown sub-problem of size n - 2a with 2a newly confirmed good coins.
    //
    // For the unknown state with good coins available, we weigh b = 3^(k-1)
    // suspects against b known-good coins. Imbalance tells us the direction
    // (all b suspects are light-only or heavy-only), giving a signed
    // sub-problem of size b. Balance eliminates those b suspects entirely,
    // leaving n - b unknowns. The capacity with good coins is (3^k + 1) / 2,
    // versus (3^k - 1) / 2 without.
    //
    // For the signed state with L light-suspects and H heavy-suspects
    // (total T), we put s = (T + 1) / 3 coins on each pan, mixing light and
    // heavy suspects so that each of the three outcomes (<, =, >) yields a
    // signed sub-problem of size roughly T/3. Specifically, we place h
    // heavy-suspects and l = s - h light-suspects on each side (with h chosen
    // so 2h <= H and 2l <= L). Left-heavier implicates heavy coins on the
    // left and light coins on the right; left-lighter implicates the
    // opposite; balance implicates the off-scale remainder.
    //
    // The base cases end up being:
    //     tot = 1 is the fake.
    //     tot = 2 same-direction weighs one against the other.
    //     tot = 2 mixed weighs a suspect against a known-good coin.
    //
    // An interesting note is that this is a fairly popular problem from quant
    // interviews and appearing in Heard on The Street book as question 1.18,
    // but the solutions given there also tries to identify if the coin is
    // heavier or lighter (and not only finds the outlier). This makes the
    // optimum log3(2n+3) instead, which might be different for say N=13. It's
    // still a good read and it has other nice puzzles:
    //
    // https://www.amazon.com/Heard-Street-Quantitative-Questions-Interviews/dp/0994103867

    vector<int> coins(n);
    iota(coins.begin(), coins.end(), 1);

    int w = 0;
    while((pow3(w) - 1) / 2 < n) {
        w++;
    }

    cout << "need " << w << " weighings\n";
    Solution* root = Solution::build_unknown(coins, {});
    root->print(0);
}

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

    int T = 1;
    // cin >> T;
    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.