library_checker/number_theory/
rational_approximation.rs

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