<|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++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

int n;

/*
    Compute 3^k.

    Here k is small because n <= 100, so integer arithmetic is safe.
*/
int pow3(int k) {
    int result = 1;
    for (int i = 0; i < k; i++) {
        result *= 3;
    }
    return result;
}

/*
    Print one weighing instruction.

    Example:
        weigh 1+2+3 vs 4+5+6
*/
void print_weighing(const vector<int>& left, const vector<int>& right, int level) {
    cout << string(level * 2, ' ') << "weigh ";

    for (int i = 0; i < (int)left.size(); i++) {
        if (i > 0) cout << "+";
        cout << left[i];
    }

    cout << " vs ";

    for (int i = 0; i < (int)right.size(); i++) {
        if (i > 0) cout << "+";
        cout << right[i];
    }

    cout << "\n";
}

/*
    A node of the decision tree.

    A node is either:
    - a leaf: fake_coin > 0
    - an internal weighing node: fake_coin == 0
*/
struct Node {
    vector<int> lhs;
    vector<int> rhs;

    Node* less_branch;
    Node* equal_branch;
    Node* greater_branch;

    int fake_coin;

    /*
        Constructor for an internal weighing node.
    */
    Node(const vector<int>& left, const vector<int>& right) {
        lhs = left;
        rhs = right;

        less_branch = nullptr;
        equal_branch = nullptr;
        greater_branch = nullptr;

        fake_coin = 0;
    }

    /*
        Constructor for a leaf node.
    */
    Node(int coin) {
        fake_coin = coin;

        less_branch = nullptr;
        equal_branch = nullptr;
        greater_branch = nullptr;
    }

    /*
        Build a tree for an unknown-direction state.

        suspects:
            coins that may be fake, direction unknown

        known_good:
            coins known to be genuine
    */
    static Node* build_unknown(
        const vector<int>& suspects,
        const vector<int>& known_good
    );

    /*
        Build a 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:
            known genuine coins
    */
    static Node* build_signed(
        const vector<int>& light,
        const vector<int>& heavy,
        const vector<int>& known_good
    );

    /*
        Recursively print the script.

        Only existing branches are printed, which automatically avoids
        impossible cases.
    */
    void print_tree(int level) const {
        string indent(level * 2, ' ');

        if (fake_coin > 0) {
            cout << indent << "fake " << fake_coin << "\n";
            return;
        }

        print_weighing(lhs, rhs, level);

        if (less_branch != nullptr) {
            cout << indent << "case <:\n";
            less_branch->print_tree(level + 1);
        }

        if (equal_branch != nullptr) {
            cout << indent << "case =:\n";
            equal_branch->print_tree(level + 1);
        }

        if (greater_branch != nullptr) {
            cout << indent << "case >:\n";
            greater_branch->print_tree(level + 1);
        }

        cout << indent << "end\n";
    }
};

Node* Node::build_unknown(
    const vector<int>& suspects,
    const vector<int>& known_good
) {
    int sz = (int)suspects.size();

    /*
        No suspects means this branch is impossible.
    */
    if (sz == 0) {
        return nullptr;
    }

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

    /*
        Case 1:
        We already have known genuine coins.

        We can compare suspect coins directly against genuine coins.
    */
    if (!known_good.empty()) {
        int k = 0;

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

        /*
            Number of suspects to weigh against genuine coins.
        */
        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
        );

        Node* node = new Node(weighed, good_on_scale);

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

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

        /*
            If equal, weighed suspects are genuine and the fake is among
            the remaining suspects.
        */
        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;
    }

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

        Capacity:
            (3^k - 1) / 2
    */
    int k = 0;
    while ((pow3(k) - 1) / 2 < sz) {
        k++;
    }

    /*
        Number of coins to place on each pan.

        We keep at least one coin off the scale whenever possible,
        because after an imbalance, off-scale coins are known genuine.
    */
    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()
    );

    Node* node = new 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_branch = build_signed(left, right, off);

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

    /*
        If equal, weighed coins are genuine,
        and the fake is among off-scale coins.
    */
    if (!off.empty()) {
        vector<int> new_good;
        new_good.insert(new_good.end(), left.begin(), left.end());
        new_good.insert(new_good.end(), right.begin(), right.end());

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

    return node;
}

Node* Node::build_signed(
    const vector<int>& light,
    const vector<int>& heavy,
    const vector<int>& known_good
) {
    int L = (int)light.size();
    int H = (int)heavy.size();
    int total = L + H;

    /*
        Impossible branch.
    */
    if (total == 0) {
        return nullptr;
    }

    /*
        Only one possible fake coin remains.
    */
    if (total == 1) {
        if (!light.empty()) {
            return new Node(light[0]);
        } else {
            return new Node(heavy[0]);
        }
    }

    /*
        Special handling for two signed suspects.
    */
    if (total == 2) {
        /*
            Both are heavy-suspects.

            Weigh them against each other:
            - left heavier means left coin is fake
            - left lighter means right coin is fake
        */
        if (L == 0) {
            Node* node = new Node(vector<int>{heavy[0]}, vector<int>{heavy[1]});

            node->less_branch = new Node(heavy[1]);
            node->greater_branch = new Node(heavy[0]);

            return node;
        }

        /*
            Both are light-suspects.

            Weigh them against each other:
            - left lighter means left coin is fake
            - left heavier means right coin is fake
        */
        if (H == 0) {
            Node* node = new Node(vector<int>{light[0]}, vector<int>{light[1]});

            node->less_branch = new Node(light[0]);
            node->greater_branch = new Node(light[1]);

            return node;
        }

        /*
            One light-suspect and one heavy-suspect.

            Compare the light-suspect with a known genuine coin.
            If it is lighter, it is fake.
            If equal, the heavy-suspect must be fake.
        */
        Node* node = new Node(vector<int>{light[0]}, vector<int>{known_good[0]});

        node->less_branch = new Node(light[0]);
        node->equal_branch = new Node(heavy[0]);

        return node;
    }

    /*
        General signed case.

        Split the possible signed candidates into three roughly equal groups.
    */
    int s = (total + 1) / 3;

    /*
        Choose how many heavy-suspects to place 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 to put l on each pan,
        reduce l and increase h.
    */
    if (2 * l > L) {
        l = L / 2;
        h = s - l;
    }

    vector<int> left_pan;
    vector<int> right_pan;

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

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

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

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

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

    vector<int> less_heavy(
        heavy.begin() + h,
        heavy.begin() + 2 * h
    );

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

    vector<int> greater_light(
        light.begin() + l,
        light.begin() + 2 * l
    );

    /*
        If equal:
            all weighed signed suspects are eliminated.
    */
    vector<int> equal_light(
        light.begin() + 2 * l,
        light.end()
    );

    vector<int> equal_heavy(
        heavy.begin() + 2 * h,
        heavy.end()
    );

    Node* node = new Node(left_pan, right_pan);

    node->less_branch = build_signed(less_light, less_heavy, known_good);
    node->equal_branch = build_signed(equal_light, equal_heavy, known_good);
    node->greater_branch = build_signed(greater_light, greater_heavy, known_good);

    return node;
}

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

    cin >> n;

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

    /*
        Compute the optimal worst-case number of weighings.
    */
    int w = 0;
    while ((pow3(w) - 1) / 2 < n) {
        w++;
    }

    cout << "need " << w << " weighings\n";

    Node* root = Node::build_unknown(coins, vector<int>());
    root->print_tree(0);

    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()
```