<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

306. Balance
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



You have n coins, exactly one of those being fake (weighing different from all others). You have a balance which allows you to compare two groups of coins. Determine the fake coin in such a way that the number of weighings in the worst case is minimum possible.

Adhere to the output format shown below. Note that you must not describe impossible cases (i.e., in the example output there is no "case = for "weigh 1+2 vs 3+4 because the pans will never be equal there). For every weighing the numbers of coins on both pans should be equal, and no coin should be simultaneously put on both pans.

Input
The input file contains the only integer n (3 ≤ n ≤ 100).

Output
Output the required script.

Example(s)
sample input
sample output
4
need 2 weighings
weigh 1 vs 2
case <:
  weigh 1+2 vs 3+4
  case <:
    fake 1
  case >:
    fake 2
  end
case =:
  weigh 1 vs 3
  case =:
    fake 4
  case <:
    fake 3
  case >:
    fake 3
  end
case >:
  weigh 1+2 vs 4+3
  case >:
    fake 1
  case <:
    fake 2
  end
end

<|response|>
## 1. Abridged problem statement

We have `n` coins, exactly one of them is fake. The fake coin may be either lighter or heavier, but we only need to determine **which coin** is fake.

Using a balance scale, output an optimal decision script that identifies the fake coin with the minimum possible worst-case number of weighings.

Each weighing must compare two disjoint groups of equal size. The output script must contain only possible outcome branches.

---

## 2. Key observations needed to solve the problem

### Observation 1: Optimal number of weighings

For this version of the fake coin problem, where we only need to identify the coin and not whether it is lighter or heavier, the maximum number of coins solvable in `w` weighings is

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

Therefore the minimum required number of weighings is the smallest `w` such that

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

---

### Observation 2: Two kinds of states are useful

During the decision process we maintain one of two types of subproblems.

---

#### Type 1: Unknown-direction state

We have some suspect coins, and each suspect may be either lighter or heavier.

We may also have some coins already known to be genuine.

Represent this as:

```text
unknown(suspects, known_good)
```

---

#### Type 2: Signed state

Sometimes, after an imbalance, we know the possible direction of each suspect.

For example, if left pan is lighter, then:

- coins on the left could be fake and lighter,
- coins on the right could be fake and heavier.

Represent this as:

```text
signed(light_suspects, heavy_suspects, known_good)
```

Where:

- `light_suspects`: coins that can only be fake if they are lighter,
- `heavy_suspects`: coins that can only be fake if they are heavier.

---

### Observation 3: In a signed state, one weighing can split possibilities into three groups

Suppose we have signed suspects.

If we put some heavy-suspects and light-suspects on both pans:

- result `<` keeps only suspects consistent with left pan being lighter,
- result `>` keeps only suspects consistent with left pan being heavier,
- result `=` eliminates all weighed suspects.

So we can split signed possibilities into roughly three equal parts.

---

### Observation 4: Known genuine coins are very useful

If we already know some good coins, then in an unknown-direction state we can compare suspect coins directly against known genuine coins.

For example:

```text
weigh suspects vs known_good
```

Then:

- if suspect side is lighter, fake is among those suspects and is lighter,
- if suspect side is heavier, fake is among those suspects and is heavier,
- if equal, those suspects are genuine.

---

## 3. Full solution approach based on the observations

We build a decision tree recursively.

Each internal node is a weighing. Each child corresponds to one possible result:

```text
case <:
case =:
case >:
```

Branches that cannot happen are not printed.

---

### Function `build_unknown(suspects, known_good)`

This handles the case where suspects may be either lighter or heavier.

#### Base case

If there is only one suspect, it must be fake:

```text
fake x
```

---

### Case A: We have known genuine coins

Let `sz = number of suspects`.

Find the smallest `k` such that:

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

Then weigh up to

```text
3^(k - 1)
```

suspects against the same number of known genuine coins.

If the suspect side is lighter, recurse into a signed state where those suspects are light-suspects.

If the suspect side is heavier, recurse into a signed state where those suspects are heavy-suspects.

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

---

### Case B: No known genuine coins

This is the initial situation.

Find the smallest `k` such that:

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

Put `a` suspects on the left pan and `a` other suspects on the right pan, where roughly:

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

The remaining suspects are left off the scale.

If the left pan is lighter:

- left-pan coins may be light fake,
- right-pan coins may be heavy fake,
- off-scale coins are genuine.

If the left pan is heavier, the symmetric case happens.

If the scale balances:

- weighed coins are genuine,
- the fake is among off-scale coins.

---

### Function `build_signed(light, heavy, known_good)`

This handles the case where each suspect already has a known possible direction.

Let:

```text
total = len(light) + len(heavy)
```

#### Base cases

If `total == 1`, that coin is fake.

If `total == 2`, handle directly:

- two heavy suspects: weigh them against each other,
- two light suspects: weigh them against each other,
- one light and one heavy suspect: compare the light suspect against a known genuine coin.

---

### General signed case

We split the signed possibilities into three almost equal groups.

Let:

```text
s = (total + 1) / 3
```

We put `s` suspect-cases worth of coins on the left pan and `s` on the right pan.

The placement is chosen so that:

- `<` branch contains about `s` possibilities,
- `>` branch contains about `s` possibilities,
- `=` branch contains the remaining possibilities.

Then recurse.

---

### Correctness

The recursion preserves exactly the set of possibilities consistent with the outcomes observed so far.

- In unknown states, an imbalance determines the fake coin's possible direction.
- A balanced weighing proves all weighed suspects genuine.
- In signed states, each balance outcome corresponds to exactly one subset of signed suspects.
- The recursion stops only when one coin is forced to be fake.

Since the construction uses the smallest `w` satisfying

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

the produced script has optimal worst-case depth.

---

## 4. 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;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


def pow3(k):
    """
    Return 3^k.

    n <= 100, so k is very small.
    """
    result = 1

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

    return result


def format_side(coins):
    """
    Format one side of the scale.

    Example:
        [1, 2, 3] -> "1+2+3"
    """
    return "+".join(map(str, coins))


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

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

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

        # Coins on the 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 equal balance.
        self.equal = None

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

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

        Only non-None branches are printed, which means impossible cases
        are automatically skipped.
        """
        indent = "  " * level

        if self.fake is not None:
            out.append(f"{indent}fake {self.fake}")
            return

        out.append(
            f"{indent}weigh {format_side(self.lhs)} vs {format_side(self.rhs)}"
        )

        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, direction unknown.

    known_good:
        Coins known to be genuine.
    """
    sz = len(suspects)

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

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

    # Case 1:
    # We already have genuine coins.
    if known_good:
        k = 0

        # Capacity with known genuine coins:
        #     (3^k + 1) / 2
        while (pow3(k) + 1) // 2 < sz:
            k += 1

        # Number of suspects to compare directly with genuine coins.
        b = min(pow3(k - 1), sz)

        weighed = suspects[:b]
        remaining = suspects[b:]
        good_on_scale = known_good[:b]

        node = Node(weighed, good_on_scale)

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

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

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

        return node

    # Case 2:
    # No known genuine coins.
    # This is the initial type of state.
    k = 0

    # Capacity without known genuine coins:
    #     (3^k - 1) / 2
    while (pow3(k) - 1) // 2 < sz:
        k += 1

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

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

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

    left = suspects[:a]
    right = suspects[a:2 * a]
    off = suspects[2 * a:]

    node = Node(left, right)

    # If left pan is lighter:
    # - left coins may be light fake
    # - right coins may be heavy fake
    # Off-scale coins are genuine in this branch.
    node.less = build_signed(left, right, off)

    # If left pan is heavier:
    # - right coins may be light fake
    # - left coins may be heavy fake
    node.greater = build_signed(right, left, off)

    # If equal, weighed coins are genuine,
    # and the fake is among off-scale coins.
    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 can only be fake if lighter.

    heavy:
        Coins that can only be fake if heavier.

    known_good:
        Coins known to be genuine.
    """
    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 handling for two signed suspects.
    if total == 2:
        # Both are heavy-suspects.
        if L == 0:
            node = Node([heavy[0]], [heavy[1]])

            # Left lighter means right heavy-suspect is fake.
            node.less = Node(fake=heavy[1])

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

            return node

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

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

            # Left heavier means right light-suspect is fake.
            node.greater = Node(fake=light[1])

            return node

        # One light-suspect and one heavy-suspect.
        # Compare the light-suspect against a known genuine coin.
        node = Node([light[0]], [known_good[0]])

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

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

        return node

    # General signed case.
    # Split possibilities into three roughly equal parts.
    s = (total + 1) // 3

    # Put h heavy-suspects on each pan.
    h = min(s, H // 2)

    # Fill remaining positions with light-suspects.
    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

    left_pan = []
    right_pan = []

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

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

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

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

    # If left pan is lighter:
    # possible suspects are:
    # - light-suspects on left
    # - heavy-suspects on right
    less_light = light[:l]
    less_heavy = heavy[h:2 * h]

    # If left pan is heavier:
    # possible suspects are:
    # - heavy-suspects on left
    # - light-suspects on right
    greater_heavy = heavy[:h]
    greater_light = light[l:2 * l]

    # If equal:
    # all weighed signed suspects are eliminated.
    equal_light = light[2 * l:]
    equal_heavy = heavy[2 * h:]

    node = Node(left_pan, right_pan)

    node.less = build_signed(less_light, less_heavy, known_good)
    node.equal = build_signed(equal_light, equal_heavy, known_good)
    node.greater = build_signed(greater_light, greater_heavy, known_good)

    return node


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

    coins = list(range(1, n + 1))

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

    out = []
    out.append(f"need {w} weighings")

    root = build_unknown(coins, [])
    root.print_tree(0, out)

    sys.stdout.write("\n".join(out))


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