競プロ典型 016

https://atcoder.jp/contests/typical90/tasks/typical90_p

A, B, Cの中で一番大きいものが何個使うか固定して、残りで一番少ない個数を調べます。

// Gravy Jobs
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// library ////////////////////

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 gcd(m: i64, n: i64) -> i64 {
    if n == 0 {
        m
    }
    else {
        gcd(n, m % n)
    }
}

// Ax + By = 1
fn solve(A: i64, B: i64) -> (i64, i64) {
    if A == 0 {
        (0, 1)
    }
    else {
        // Ax + (qA + r)y = 1
        // ry + A(x + qy) = 1
        let q = B / A;
        let r = B % A;
        let (x1, y1) = solve(r, A);
        (y1-q*x1, x1)
    }
}


//////////////////// process ////////////////////

fn read_input() -> (i64, i64, i64, i64) {
    let N: i64 = read();
    let v = read_vec();
    let (A, B, C) = (v[0], v[1], v[2]);
    (N, A, B, C)
}

fn sort(A: i64, B: i64, C: i64) -> (i64, i64, i64) {
    let mut v: Vec<i64> = vec![A, B, C];
    v.sort();
    (v[0], v[1], v[2])
}

fn min_coins(A: i64, B: i64, N: i64) -> Option<i64> {
    let d = gcd(A, B);
    if N % d != 0 {
        return None
    }
    
    let (A1, B1, N1) = (A / d, B / d, N / d);
    let (x1, y1) = solve(A1, B1);
    let (x2, y2) = (x1*N1, y1*N1);
    let r = x2 % B1;
    let x3 = if r >= 0 { r } else { r + B1 };
    let y3 = y2 + (x2 - x3) / B1 * A1;
    if y3 >= 0 {
        Some(x3 + y3)
    }
    else {
        None
    }
}

fn F(N: i64, A: i64, B: i64, C: i64) -> i64 {
    let (P, Q, R) = sort(A, B, C);
    let max_i = min(9999, N / R + 1);
    let mut min_s = N / P + 1;
    for i in 0..max_i+1 {
        match min_coins(P, Q, N - i*R) {
            Some(s) => min_s = min(min_s, i + s),
            None         => ()
        }
    }
    min_s
}

fn main() {
    let (N, A, B, C) = read_input();
    println!("{}", F(N, A, B, C))
}