If the denominator \(D\) of the representation of \(r\) as a fraction is no greater than \(N\), then the answer is obvious. From now on, we assume that \(N\lt D\).

For a positive integer \(X\), let \(T_X\) be a subtree of the Stern-Brocot tree whose vertices consist of those whose:

• values are in the segment \([0,1]\), and
• representations as irreducible fractions \(p/q\) satisfy \(q\leq X\).

This forms a binary search tree for all \(X\).

Among the nodes of \(T _ N\), let \(x\) be the maximum one less than \(r\), and \(y\) be the minimum one greater than \(r\).

For example, when \(N=5\) and \(r=0.45\), we can illustrate \(T _ N\), \(x\), and \(y\) as follows:

Each of \(x\) and \(y\) coincides with a node on the path from the root \(\dfrac01\) to \(r\) on \(T _ D\).

For the continued fraction expansion \([0;a _ 1,a _ 2,\ldots,a _ K,a _ {K+1}=1]\) of \(r\), each node on the path from the root to \(r\) is an irreducible fraction that can be represented as \([0;a _ 1,\ldots,a _ k,n]\ (0\leq k\leq K,1\leq n\leq a _ {k+1})\) (Proof omitted).
For a fixed \(k\), the ordering of \([0;a _ 1,\ldots,a _ k,n]\ (1\leq n\leq a _ {k+1})\) and \(r\) is only dependent on the parity of \(k\), and the larger \(n\) is, the closer to \(r\). For a fixed parity of \(k\), the larger \(k\) is, the closer to \(r\). Therefore, \(x\) and \(y\) are \([0;a _ 1,\ldots,a _ k,n]\) and \([0;a _ 1,\ldots,a _ k]\), respectively, for the lexicographically largest \((k,n)\ (0\leq k\leq K,1\leq n\leq a _ {k+1})\) such that the denominator of the irreducible fraction representation of \([0;a _ 1,\ldots,a _ k,n]\) does not exceed \(N\).

Therefore, \(x\) and \(y\) can be identified once we obtain the continued fraction expansion of \(r\).

The sought value is either \(x\) or \(y\) (represented as a pair of integers that are the numerator and denominator). The answer can be determined by comparing \(|r-x|\) and \(|r-y|\).
Note that it is troublesome or difficult to determine the ordering between them only with \(64\operatorname{bit}\) integers, double-precision floating point numbers, or extended double-precision floating point numbers (though the sample code adopts \(64\operatorname{bit}\) integers). It simplifies implementation to use a number type with more digits or precision.

The following is sample code. The implementation finds the continued fraction expansion of \(r\) while finding the numerator and denominator of the preliminary expansion.

Even without representing \(r\) as an irreducible fraction, one can still determine if \(D\leq N\) by checking if the continued fraction expansion stops before the preliminary denominator exceeds \(N\).

#include <utility>
#include <vector>
#include <iostream>
#include <ranges>
#include <atcoder/modint>
#include <atcoder/math>

// Given irreducible fractions x = a/b and y = c/d and a rational number r = p/q (x < r < y),
// determines which of a/b and c/d is closer to p/q.
// Since p/q - a/b < c/d - a/b = 1 / bd,
// the integer (p/q - a/b) * qbd = pbd - qad falls into the range (0, q).
// We use this property to evaluate it on some modulus and reconstruct the original value.
template<class Fraction>
bool compare(const Fraction &r, const Fraction &x, const Fraction &y) {
    const auto&[p, q]{r};
    const auto&[a, b]{x};
    const auto&[c, d]{y};

    using modint1 = atcoder::static_modint<1000000007>;
    using modint2 = atcoder::static_modint<1000000009>;

    std::vector<long long> reminder, modulo;
    reminder.emplace_back((modint1{p} * b * d - modint1{q} * a * d).val());
    modulo.emplace_back(modint1::mod());

    reminder.emplace_back((modint2{p} * b * d - modint2{q} * a * d).val());
    modulo.emplace_back(modint2::mod());

    // |r-x| <= |r-y| iff (p/q - a/b) * qbd <= q/2
    return atcoder::crt(reminder, modulo).first * 2 <= r.second;
}

int main() {
    using namespace std;
    using fraction = pair<unsigned long, unsigned long>;

    string r_str;
    unsigned long N;
    cin >> r_str >> N;

    // Make `r` a rational number
    fraction r{0, 1};
    auto&&[p, q]{r};

    for (const auto digit : r_str | views::drop(2)) {
        (p *= 10) += digit - '0';
        q *= 10;
    }

    // Make it irreducible
    {
        const auto g{gcd(p, q)};
        p /= g;
        q /= g;
    }

    // If the numerator is always no less than N, that is the answer
    if (q <= N) {
        cout << p << " " << q << endl;
        return 0;
    }

    // Find the maximum x and minimum y such that x < r < y
    const auto&[x, y]{[](const unsigned long N, fraction frac) -> pair<fraction, fraction> {
        auto&&[p, q]{frac};

        pair<unsigned long, unsigned long> numerator{1, 0}, denominator{0, 1};
        auto&&[n1, n2]{numerator};
        auto&&[d1, d2]{denominator};

        bool depth_parity{};
        // continued fraction expansion
        while (q) {
            const auto quo{p / q};
            const auto max_q{d1 ? (N - d2) / d1 : (N - n2) / n1};

            // Once it exceeds N, we obtain x and y
            if (quo >= max_q)
                if (depth_parity)
                    return {{n1, d1}, {n1 * max_q + n2, d1 * max_q + d2}};
                else
                    return {{n1 * max_q + n2, d1 * max_q + d2}, {n1, d1}};

            numerator = make_pair(n1 * quo + n2, n1);
            denominator = make_pair(d1 * quo + d2, d1);
            frac = make_pair(q, p % q);

            depth_parity ^= 1;
        }
        return {};
    }(N, r)};

    if (compare(r, x, y)) // If r <= (x+y)/2,
        // print x;
        cout << x.first << " " << x.second << endl;
    else // otherwise,
        // print y.
        cout << y.first << " " << y.second << endl;

    return 0;
}