Skip to main content

library_checker/number_theory/
rational_approximation.rs

1use competitive::prelude::*;
2use competitive::{algorithm::rational_binary_search, num::URational};
3
4#[verify::library_checker("rational_approximation")]
5pub fn rational_approximation(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(t);
8    for _ in 0..t {
9        sc!(n: u64, x: u64, y: u64);
10        let x = URational::new_unchecked(x, y);
11        let sbt = rational_binary_search::<u64>(|&a| a <= x, n);
12        if matches!(sbt.l.cmp(&x), std::cmp::Ordering::Equal) {
13            pp!(sbt.l.num, sbt.l.den, sbt.l.num, sbt.l.den);
14        } else {
15            pp!(sbt.l.num, sbt.l.den, sbt.r.num, sbt.r.den);
16        }
17    }
18}