AtCoder Beginner Contest 382 D

https://atcoder.jp/contests/abc381/tasks/abc381_d

入力例1なら10ごとに離れた位置だと1 11 21なので2だけ余裕があります。それを3つに分けます。分割統治法を使うとよいです。

// Keep Distance
#![allow(non_snake_case)]


//////////////////// 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()
}


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

fn read_input() -> (i32, i32) {
    let v: Vec<i32> = read_vec();
    let (N, M) = (v[0], v[1]);
    (N, M)
}

fn DC(N: i32, margin: i32) -> Vec<Vec<i32>> {
    let mut vs: Vec<Vec<i32>> = vec![];
    if N == 1 {
        for m in 0..margin+1 {
            vs.push(vec![m])
        }
    }
    else if N % 2 == 1 {
        let vs1 = DC(N - 1, margin);
        for v1 in vs1.into_iter() {
            let m1 = v1.iter().map(|&e| e).sum::<i32>();
            for m2 in 0..margin-m1+1 {
                let mut v = v1.clone();
                v.push(m2);
                vs.push(v)
            }
        }
    }
    else {
        let vs1 = DC(N / 2, margin);
        let vs2 = vs1.clone();
        for v1 in vs1.into_iter() {
            let m1 = v1.iter().map(|&e| e).sum::<i32>();
            for v2 in vs2.iter() {
                let m2 = v2.iter().map(|&e| e).sum::<i32>();
                if m1 + m2 <= margin {
                    let mut v = v1.clone();
                    v.extend(v2);
                    vs.push(v)
                }
            }
        }
    }
    vs
}

fn F(N: i32, M: i32) {
    let margin = M - (N - 1) * 10 - 1;
    let vs: Vec<Vec<i32>> = DC(N, margin);
    println!("{}", vs.len());
    for v in vs.iter() {
        let mut w = vec![0; v.len()];
        w[0] = v[0] + 1;
        for i in 1..v.len() {
            w[i] = w[i-1] + 10 + v[i]
        }
        println!("{}", w.into_iter().map(|n| n.to_string()).
                                collect::<Vec<String>>().join(" "))
    }
}

fn main() {
    let (N, M) = read_input();
    F(N, M)
}