const Coin& DetectFalseCoin(const std::vector<Coin>& coins) {
    std::vector<Coin> cur = coins;

    while (cur.size() > 1) {
        int a = Weight(std::vector<Coin>(cur.begin(), cur.begin() + (cur.size() + 1) / 3), std::vector<Coin>(cur.begin() + (cur.size() + 1) / 3, cur.begin() + ((cur.size() + 1) / 3) * 2));
        if (a == -1) {
            cur = std::vector<Coin>(cur.begin(), cur.begin() + (cur.size() + 1) / 2);
        } else if (a == 1) {
            cur = std::vector<Coin>(cur.begin() + (cur.size() + 1) / 3, cur.begin() + ((cur.size() + 1) / 3) * 2);
        } else {
            cur = std::vector<Coint>(cur.begin() + ((cur.size() + 1) / 3) * 2, cur.end());
        }
    }

    return cur[0];
}