結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー urectanc
提出日時 2025-10-31 23:33:04
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 19 ms / 6,000 ms
コード長 2,378 bytes
コンパイル時間 12,928 ms
コンパイル使用メモリ 401,660 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-31 23:33:21
合計ジャッジ時間 14,619 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;

const N: usize = 81181819;
const K: usize = 9;
const M: usize = 8 * K;

fn main() {
    let solver = Solver::new();

    input! { t: usize }
    for _ in 0..t {
        input! { n: usize }
        let ans = solver.solve(N - n);
        println!("{}", ans.len());
        println!(
            "{}",
            ans.iter()
                .map(ToString::to_string)
                .collect::<Vec<_>>()
                .join("\n")
        );
    }
}

struct Solver {
    table: Vec<Option<Vec<usize>>>,
}

impl Solver {
    fn new() -> Self {
        let mut table = vec![None; M + 1];
        table[0] = Some(vec![]);
        for i in 1..=M {
            for d in [8, 1] {
                if i >= d {
                    if let Some(v) = &table[i - d] {
                        if v.len() >= K {
                            continue;
                        }
                        let mut v = v.clone();
                        v.push(d);
                        table[i] = Some(v);
                        break;
                    }
                }
            }
        }
        Self { table }
    }

    fn solve(&self, n: usize) -> Vec<usize> {
        for k in 1..10 {
            let ans = self.search(n, k);
            if let Some(ans) = ans {
                return ans;
            }
        }
        unreachable!()
    }

    fn search(&self, n: usize, k: usize) -> Option<Vec<usize>> {
        for (i, v) in self.table.iter().enumerate() {
            if n < i {
                break;
            }
            if let Some(v) = v {
                if v.len() > k {
                    continue;
                }

                if i == n {
                    assert!(v.len() <= k);
                    let mut v = v.clone();
                    v.resize(k, 0);
                    return Some(v);
                }

                if (n - i) % 10 == 0 {
                    if let Some(mut w) = self.search((n - i) / 10, k) {
                        assert_eq!(w.len(), k);

                        for a in &mut w {
                            *a *= 10;
                        }

                        for (a, b) in w.iter_mut().zip(v) {
                            *a += b;
                        }

                        return Some(w);
                    }
                }
            }
        }
        None
    }
}
0