Test/LC/rational_approximation.test.cpp

• View this file on GitHub
• Last update: 2025-07-23 20:10:46+09:00
• Problem: https://judge.yosupo.jp/problem/rational_approximation

Depends on

• 有理数で二分探索 (Src/Utility/RationalBinarySearch.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/rational_approximation"

#include "../../Src/Utility/RationalBinarySearch.hpp"

#include <iostream>
using namespace zawa;
using namespace std;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0); 
    int T;
    cin >> T;
    while (T--) {
        long long N, x, y;
        cin >> N >> x >> y;
        auto f = [&](long long a, long long b) -> bool {
            return a * y <= x * b;
        };
        auto [max_ok, min_ng] = RationalBinarySearch(f, N);
        auto [a, b] = max_ok;
        auto [c, d] = min_ng;
        if (a * y == x * b) {
            cout << a << ' ' << b << ' ' << a << ' ' << b << '\n';
        }
        else {
            cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
        }
    }
}

#line 1 "Test/LC/rational_approximation.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rational_approximation"

#line 2 "Src/Utility/RationalBinarySearch.hpp"

#include <cassert>
#include <concepts>
#include <utility>

namespace zawa {

template <class F, std::integral T>
requires std::predicate<F, T, T>
std::pair<std::pair<T, T>, std::pair<T, T>> RationalBinarySearch(F f, T n) {
    assert(f(0, 1) and !f(1, 0));
    auto dfs = [&](auto dfs, bool cur, T& p, T& q, T pp, T pq) -> void {
        if (p + pp > n or q + pq > n) return;
        if (f(p + pp, q + pq) == cur) {
            p += pp;
            q += pq;
            dfs(dfs, cur, p, q, pp << 1, pq << 1);
        }
        if (p + pp <= n and q + pq <= n and f(p + pp, q + pq) == cur) {
            p += pp;
            q += pq;
        }
    };
    T pl = 0, ql = 1, pr = 1, qr = 0;
    while (pl + pr <= n and ql + qr <= n) {
        dfs(dfs, true, pl, ql, pr, qr);
        dfs(dfs, false, pr, qr, pl, ql);
    }
    return std::pair{std::pair{pl, ql}, std::pair{pr, qr}};
}

} // namespace zawa
#line 4 "Test/LC/rational_approximation.test.cpp"

#include <iostream>
using namespace zawa;
using namespace std;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0); 
    int T;
    cin >> T;
    while (T--) {
        long long N, x, y;
        cin >> N >> x >> y;
        auto f = [&](long long a, long long b) -> bool {
            return a * y <= x * b;
        };
        auto [max_ok, min_ng] = RationalBinarySearch(f, N);
        auto [a, b] = max_ok;
        auto [c, d] = min_ng;
        if (a * y == x * b) {
            cout << a << ' ' << b << ' ' << a << ' ' << b << '\n';
        }
        else {
            cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
        }
    }
}

Back to top page