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

    while (cur.size() > 1) {
        std::vector<Coin> c1, c2, c3;
        for (size_t i = 0; i < (cur.size() + 1) / 3; ++i) {
            c1.push_back(cur[i]);
        }
        for (size_t i = (cur.size() + 1) / 3; i < ((cur.size() + 1) / 3) * 2; ++i) {
            c2.push_back(cur[i]);
        }
        for (size_t i = ((cur.size() + 1) / 3) * 2; i < cur.size(); ++i) {
            c3.push_back(cur[i]);
        }
        int a = Weight(c1, c2);
        if (a == -1) {
            cur = c1;
        } else if (a == 1) {
            cur = c2;
        } else {
            cur = c3;
        }
    }

    return cur[0];
}