ABC 426

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string X, Y;
    cin >> X >> Y;

    map<string, int> mp;
    mp["Ocelot"] = 1;
    mp["Serval"] = 2;
    mp["Lynx"] = 3;

    yesno(mp[X] >= mp[Y]);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    map<char, int> mp;
    for (char c : S) mp[c]++;

    for (auto [k, v] : mp) {
        if (v == 1) {
            cout << k << endl;
        }
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, Q;
    cin >> N >> Q;

    map<ll, ll> os;
    rep(i, N) os[i + 1] = 1;

    while (Q--) {
        ll X, Y;
        cin >> X >> Y;

        ll cnt = 0;
        vll can_delete;
        for (auto [k, v] : os) {
            if (k > X) break;
            can_delete.push_back(k);
            cnt += v;
        }
        for (auto k : can_delete) os.erase(k);
        os[Y] += cnt;
        cout << cnt << '\n';
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        ll N;
        string S;
        cin >> N >> S;

        auto ps = runLengthEncode(S);
        int sz = ps.size();

        fenwick_tree<ll> zero(sz), one(sz);
        rep(i, sz) {
            if (ps[i].first == '1') {
                one.add(i, ps[i].second);
            } else {
                zero.add(i, ps[i].second);
            }
        }

        ll ans = INF;
        rep(i, 2) {
            rep(i, sz) {
                ll cnt = 0;
                cnt += one.sum(0, i + 1);
                cnt += zero.sum(0, i) * 2;
                cnt += one.sum(i + 1, sz);
                cnt += zero.sum(i + 1, sz) * 2;
                chmin(ans, cnt);
            }
            swap(one, zero);
        }
        cout << ans << endl;
    };

    int t;
    cin >> t;
    while (t--) cal();
}

1
9 2 0 8
-3 -1 -5 -4

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal_dist = [](ll x1, ll x2, ll y1, ll y2) -> double {
        double dx = x1 - x2, dy = y1 - y2;
        return sqrtl(dx * dx + dy * dy);
    };

    auto cal = [&]() -> void {
        ll tsx, tsy, tgx, tgy;
        ll asx, asy, agx, agy;
        cin >> tsx >> tsy >> tgx >> tgy;
        cin >> asx >> asy >> agx >> agy;

        double tdist = cal_dist(tsx, tgx, tsy, tgy);
        double adist = cal_dist(asx, agx, asy, agy);

        auto takahashi_pos = [&](double t) -> pair<double, double> {
            if (t > tdist) return {tgx, tgy};

            double x = tsx + t * (tgx - tsx) / tdist;
            double y = tsy + t * (tgy - tsy) / tdist;
            return {x, y};
        };
        auto aoki_pos = [&](double t) -> pair<double, double> {
            if (t > adist) return {agx, agy};

            double x = asx + t * (agx - asx) / adist;
            double y = asy + t * (agy - asy) / adist;
            return {x, y};
        };

        auto f = [&](double tx, double ax, double ty, double ay) -> double {
            double dx = tx - ax, dy = ty - ay;
            return sqrt(dx * dx + dy * dy);
        };

        auto ternary = [&](double low, double high) -> double {
            int niter = 60;
            rep(_, niter) {
                double c1 = (low * 2 + high) / 3;
                double c2 = (low + high * 2) / 3;

                auto [tx1, ty1] = takahashi_pos(c1);
                auto [ax1, ay1] = aoki_pos(c1);
                auto [tx2, ty2] = takahashi_pos(c2);
                auto [ax2, ay2] = aoki_pos(c2);

                if (f(tx1, ax1, ty1, ay1) >= f(tx2, ax2, ty2, ay2))
                    low = c1;
                else
                    high = c2;
            }
            auto [tx, ty] = takahashi_pos(low);
            auto [ax, ay] = aoki_pos(low);
            return f(tx, ax, ty, ay);
        };

        double ans = (double)INF;

        {
            double low = 0, high = min(tdist, adist);
            chmin(ans, ternary(low, high));
        }
        {
            double low = min(tdist, adist), high = max(tdist, adist);
            chmin(ans, ternary(low, high));
        }
        printf("%.9lf\n", ans);
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}