AtCoder Beginner Contest 279 D（2）

https://atcoder.jp/contests/abc279/tasks/abc279_d

微分を使わなくても、3点の区間を倍々にしていって、3点の中で真ん中が一番時間が短ければ、そこから真ん中が一番時間が短い状態をキープしつつ区間を縮小していきます。

// Freefall
#![allow(non_snake_case)]


fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn read_input() -> (u64, u64) {
    let v = read_vec();
    (v[0], v[1])
}

fn time(g: u64, A: u64, B: u64) -> f64 {
    (A as f64) / (g as f64).sqrt() + (B * (g - 1)) as f64
}

fn find_increasing_point(g2: u64, t2: f64, A: u64, B: u64) -> u64 {
    let g3 = g2 * 2;
    let t3 = time(g3, A, B);
    if t2 < t3 {
        g2
    }
    else {
        find_increasing_point(g3, t3, A, B)
    }
}

fn find_min_time(g1: u64, g2: u64, g3: u64, A: u64, B: u64) -> f64 {
    if g1 == g2 - 1 && g2 == g3 - 1 {
        return time(g2, A, B)
    }
    let g4 = (g1 + g2) / 2;
    let g5 = (g2 + g3) / 2;
    
    let t4 = time(g4, A, B);
    let t2 = time(g2, A, B);
    let t5 = time(g5, A, B);
    if t2 <= t4 && t2 <= t5 {
        find_min_time(g4, g2, g5, A, B)
    }
    else if t4 <= t2 && t4 <= t5 {
        find_min_time(g1, g4, g2, A, B)
    }
    else {
        find_min_time(g2, g5, g3, A, B)
    }
}

fn f(A: u64, B: u64) -> f64 {
    let t1 = time(1, A, B);
    let t2 = time(2, A, B);
    if t1 < t2 {
        return t1
    }
    
    let g = find_increasing_point(2, t2, A, B);
    find_min_time(g / 2, g, g * 2, A, B)
}

fn main() {
    let v = read_input();
    println!("{}", f(v.0, v.1))
}