number/test/rational_approximation.test.cpp

• View this file on GitHub
• Last update: 2024-07-14 00:23:24+09:00
• Problem: https://judge.yosupo.jp/problem/rational_approximation

Depends on

• Rational approximation （有理数近似） (number/rational_approximation.hpp)

Code

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

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

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

    int T;
    cin >> T;
    while (T--) {
        int N, x, y;
        cin >> N >> x >> y;
        const auto [l, r] = rational_approximation<int>(N, x, y);
        const auto [lnum, lden] = l;
        const auto [rnum, rden] = r;
        cout << lnum << ' ' << lden << ' ' << rnum << ' ' << rden << '\n';
    }
}

#line 1 "number/test/rational_approximation.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rational_approximation"
#line 2 "number/rational_approximation.hpp"

#include <cassert>
#include <utility>
#include <vector>

// Rational approximation based on Stern–Brocot tree
// Input: N > 0, num >= 0, den >= 0 (num > 0 or den > 0)
// return {{p, q}, {r, s}} where p/q <= num/den <= r/s. Strictly,
// - p/q = max(n / d | n / d <= num / den, 0 <= n <= N, 1 <= d <= N)
// - r/s = min(n / d | num / den <= n / d, 0 <= n <= N, 1 <= d <= N)
template <class Int>
std::pair<std::pair<Int, Int>, std::pair<Int, Int>> rational_approximation(Int N, Int num, Int den) {
    assert(N >= 1);
    assert(num >= 0);
    assert(den >= 0);
    assert(num > 0 or den > 0);

    if (num == Int(0)) return {{Int(0), Int(1)}, {Int(0), Int(1)}}; // 0
    if (den == Int(0)) return {{Int(1), Int(0)}, {Int(1), Int(0)}}; // inf

    // p/q <= num/den <= r/s
    Int p = 0, q = 1, r = 1, s = 0;

    bool is_left = false;
    while (true) {
        Int max_steps = num / den;

        if (is_left) {
            // r + steps * p <= N
            // s + steps * q <= N

            if (p > Int(0)) max_steps = std::min(max_steps, (N - r) / p);
            max_steps = std::min(max_steps, (N - s) / q);

            r += max_steps * p;
            s += max_steps * q;
        } else {
            // p + steps * r <= N
            // q + steps * s <= N

            max_steps = std::min(max_steps, (N - p) / r);
            if (s > Int(0)) max_steps = std::min(max_steps, (N - q) / s);

            p += max_steps * r;
            q += max_steps * s;
        }

        if (is_left and !max_steps) break;

        num -= max_steps * den;

        if (num == Int(0)) {
            if (is_left) {
                return {{r, s}, {r, s}};
            } else {
                return {{p, q}, {p, q}};
            }
        }

        std::swap(num, den);
        is_left = !is_left;
    }

    return {{p, q}, {r, s}};
}
#line 3 "number/test/rational_approximation.test.cpp"

#line 5 "number/test/rational_approximation.test.cpp"
#include <iostream>
using namespace std;

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

    int T;
    cin >> T;
    while (T--) {
        int N, x, y;
        cin >> N >> x >> y;
        const auto [l, r] = rational_approximation<int>(N, x, y);
        const auto [lnum, lden] = l;
        const auto [rnum, rden] = r;
        cout << lnum << ' ' << lden << ' ' << rnum << ' ' << rden << '\n';
    }
}

Back to top page