use std::collections::HashMap;

fn fill_count(n: usize, min: usize, map: &mut HashMap<usize, usize>) -> usize {
    if n < min {
        0
    } else {
        let mut total = 0;
        let mut len = n;
        let mut count = 1;
        while len >= min {
            total += count;
            if n - len > min {
                let mut rem = (n - len) - 1;
                while rem >= min {
                    if let Some(&next) = map.get(&rem) {
                        total += next;
                    } else {
                        let sum = fill_count(rem, min, map);
                        map.insert(rem, sum);
                        total += sum;
                    }
                    rem -= 1;
                }
            }
            count += 1;
            len -= 1;
        }

        total
    }
}


fn problem_114(n: usize) -> usize {
    let mut map = HashMap::new();
    fill_count(n, 3, &mut map) + 1
}

fn problem_115() -> usize {
    let mut map = HashMap::new();
    let mut n = 100;
    while fill_count(n, 50, &mut map) + 1 < 1_000_000 {
        n += 1;
    }

    n
}

fn main() {
    println!("{}", problem_114(50));
    println!("{}", problem_115());
}