e31.rs

fn combinations(target: i32) -> usize {
    fn val(c: &[i32; 8]) -> i32 {
        c[0]*200 + c[1]*100 + c[2]*50 + c[3]*20 +
            c[4]*10 + c[5]*5 + c[6]*2 + c[7]
    }

    fn try_prefix(mut c: [i32; 8], p: usize, t: i32) -> usize {
        if p == 7 {
            c[7] = 0;
            return if val(&c) <= t {
                1
            } else {
                0
            };
        }
        
        for i in p..8 {
            c[i] = 0;
        }
        
        let mut r = 0usize;
        for i in 0.. {
            c[p] = i;
            let c = try_prefix(c.clone(), p+1, t);
            if c < 1 {
                break;
            } else {
                r += c;
            }
        }
        
        r
    }
    
    try_prefix([0i32; 8], 0, target)
}

fn main() {
    println!("{}", combinations(200));
}