結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー magurofly
提出日時 2025-10-31 21:42:08
言語 Rust
(1.83.0 + proconio)
結果
MLE  
実行時間 -
コード長 3,804 bytes
コンパイル時間 12,871 ms
コンパイル使用メモリ 400,416 KB
実行使用メモリ 797,952 KB
最終ジャッジ日時 2025-10-31 21:42:24
合計ジャッジ時間 15,597 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other MLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(dead_code, unused_imports, unused_macros, non_snake_case)]

fn main() {
  let max = 81181819;
  let mut yiwiy9_numbers = vec![];
  for i in 1 .. {
    let mut x = i;
    let mut digits = vec![];
    while x > 0 {
      digits.push([0, 1, 8][x % 3]);
      x /= 3;
    }
    let mut y = 0;
    for &d in digits.iter().rev() {
      y = y * 10 + d;
    }
    if y > max {
      break;
    }
    yiwiy9_numbers.push(y);
  }

  input! {
    T: usize,
  }
  
  for _ in 0 .. T {
    input! {
      N: usize,
    }

    
    // let mut p = vec![];

    // {    
    //   let mut n = max - N;

    //   if n == 0 {
    //     p.push(0);
    //   }

    //   // greedy
    //   while n > 0 {
    //     let y = yiwiy9_numbers[yiwiy9_numbers.partition_point(|&y| y <= n ) - 1];
    //     p.push(y);
    //     n -= y;
    //   }
    // }

    // dp
    let mut dp = HashMap::new();
    dp.insert(0, (0, 0));
    for &y in &yiwiy9_numbers {
      dp.insert(y, (1, y));
    }
    fn rec(yiwiy9_numbers: &[usize], dp: &mut HashMap<usize, (usize, usize)>, n: usize) -> usize {
      if let Some(&ans) = dp.get(&n) {
        return ans.0;
      }

      let mut ans = (INF as usize, 0);
      for &y in yiwiy9_numbers {
        if y > n {
          break;
        }
        ans.chmin((rec(yiwiy9_numbers, dp, n - y) + 1, y));
        if ans.0 <= 2 {
          break;
        }
      }

      dp.insert(n, ans);
      ans.0
    }

    rec(&yiwiy9_numbers, &mut dp, max - N);

    let mut p = vec![];
    let mut n = max - N;
    if n == 0 {
      p.push(0);
    }
    while n > 0 {
      let (_, y) = dp[&n];
      p.push(y);
      n -= y;
    }

    say(p.len());
    say(p.iter().implode("\n"));
  }
}

type Int = i64;
const MOD: Int = 998244353;
// const MOD: Int = 1_000_000_007;
const INF: Int = 1_000_000_000_000_000_000;
const YESNO: [&'static str; 2] = ["Yes", "No"];

use proconio::{input, input_interactive, marker::{Chars, Bytes, Usize1}};
use std::*;
use std::ops::*;
use collections::*; // (BTree|Hash)(Set|Map), BinaryHeap, VecDeque, LinkedList
use cmp::{self, Reverse}; // cmp::{min, max}

fn yes() { println!("{}", YESNO[0]); }
fn no() { println!("{}", YESNO[1]); }
fn yesno(c: bool) { println!("{}", if c { YESNO[0] } else { YESNO[1] }); }
fn say<T: std::fmt::Display>(x: T) -> T { println!("{}", x); x }
fn neighbor4<F: FnMut(usize, usize)>(i: usize, j: usize, h: usize, w: usize, mut f: F) { if i > 0 { (f)(i - 1, j); } if i < h - 1 { (f)(i + 1, j); } if j > 0 { (f)(i, j - 1); } if j < w - 1 { (f)(i, j + 1); } }

trait MyItertools : Iterator + Sized {
  fn to_vec(self) -> Vec<Self::Item> { self.collect::<Vec<_>>() }
  fn to_vec_rev(self) -> Vec<Self::Item> { let mut v = self.collect::<Vec<_>>(); v.reverse(); v }
  fn tally(self) -> HashMap<Self::Item, usize> where Self::Item: Copy + Eq + hash::Hash { let mut counts = HashMap::new(); self.for_each(|item| *counts.entry(item).or_default() += 1 ); counts }
  fn count_if<P: Fn(Self::Item) -> bool>(self, predicate: P) -> usize { self.map(predicate).filter(|&x| x ).count() }
  fn implode(self, sep: &str) -> String where Self::Item: std::string::ToString { self.map(|x| x.to_string()).to_vec().join(sep) }
  fn mex(self, gen: impl IntoIterator<Item = Self::Item>) -> Self::Item where Self::Item: Ord { let mut v = self.collect::<Vec<_>>(); v.sort(); v.dedup(); let mut it = v.into_iter(); gen.into_iter().find(|a| if let Some(x) = it.next() { a != &x } else { true }).unwrap() }
}
impl<T: ?Sized> MyItertools for T where T: Iterator + Sized {}

trait MyOrd : PartialOrd + Sized {
  fn chmax(&mut self, mut rhs: Self) -> bool { if self < &mut rhs { *self = rhs; true } else { false } }
  fn chmin(&mut self, mut rhs: Self) -> bool { if self > &mut rhs { *self = rhs; true } else { false } }
}
impl<T: Sized + PartialOrd> MyOrd for T {}
0