Numerot

warning: unused import: `BTreeMap`
 --> input/code.rs:2:24
  |
2 | use std::collections::{BTreeMap, HashMap};
  |                        ^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `Instant`
 --> input/code.rs:5:27
  |
5 | use std::time::{Duration, Instant};
  |                           ^^^^^^^

warning: unused variable: `first`
   --> input/code.rs:140:32
    |
140 | fn recurse(n: i64, max_d: i64, first: bool) -> (i64, u64) {
    |                                ^^^^^ help: consider prefixing with an underscore: `_first`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: function is never used: `digits`
  --> input/code.rs:25:4
   |
25 | fn digits(i: u64) -> DigitIterator {
   |    ^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: function is never used: `brute_f_until`
  --> input/code.rs:29:4
   |
29 | fn brute_f_until(n: u64) -> Vec<u64> {
   |    ^^^^^^^^^^^^^

warning: function is never used: `greed...

use std::cell::RefCell;
use std::collections::{BTreeMap, HashMap};
use std::io::BufRead;
use std::iter::{FusedIterator, Iterator};
use std::time::{Duration, Instant};

struct DigitIterator(Option<u64>);
impl Iterator for DigitIterator {
    type Item = u64;
    fn next(&mut self) -> Option<u64> {
        if let Some(ref mut i) = self.0 {
            let r = *i % 10;
            *i /= 10;
            if *i == 0 {
                self.0 = None;
            }
            Some(r)
        } else {
            None
        }
    }
}
impl FusedIterator for DigitIterator {}

fn digits(i: u64) -> DigitIterator {
    DigitIterator(Some(i))
}

fn brute_f_until(n: u64) -> Vec<u64> {
    let mut res = Vec::with_capacity(n as usize + 1);
    res.push(0);

    for i in 1..=n {
        res.push(
            1 + digits(i)
                .filter(|d| *d > 0)
                .map(|d| res[(i - d) as usize])
                .min()
                .unwrap(),
        );
    }

    res
}

fn greedy_f_brute(n: u64) -> u64 {
    let mut res = 0;
    let mut n = n;
    while n > 0 {
        n -= digits(n).max().unwrap();
        res += 1;
    }
    res
}

fn greedy_f_brute_2(n: u64, max_d: u64) -> u64 {
    let mut res = 0;
    let mut n = n as i64;
    while n > 0 {
        n -= digits(n as u64).max().unwrap().max(max_d) as i64;
        res += 1;
    }
    res
}

fn log10(n: i64) -> i64 {
    // if n <= 9 {
    //     0
    // } else {
    //     1 + log10(n / 10)
    // }
    let mut res = 0;
    let mut n = n;
    while n > 9 {
        n /= 10;
        res += 1;
    }
    res
}

fn pow10(e: i64) -> i64 {
    [
        1,
        10,
        100,
        1000,
        10000,
        100000,
        1000000,
        10000000,
        100000000,
        1000000000,
        10000000000,
        100000000000,
        1000000000000,
        10000000000000,
        100000000000000,
        1000000000000000,
        10000000000000000,
        100000000000000000,
        1000000000000000000,
    ][e as usize]
}

std::thread_local! {
    static MEM: RefCell<HashMap<(i64, i64), (i64, u64)>> = Default::default();
}

// static mut MEM: Option<HashMap<(u64, u64), (i64, u64)>> = None;
static mut TIME: Duration = Duration::from_nanos(1);

fn reduce_n(n: i64, max_d: i64) -> (i64, u64) {
    std::thread_local! {
        static MEM: RefCell<HashMap<(i64, i64), (i64, u64)>> = Default::default();
    }

    if let Some(res) = MEM.with(|mem| mem.borrow().get(&(n, max_d)).copied()) {
        return res;
    }

    let (o_n, o_max_d) = (n, max_d);
    if n > 0 {
        let mut n = n;
        let mut ops = 0;
        let p10 = pow10(log10(n));
        let d = n / p10;
        let (offset, rops) = recurse(n - d * p10, max_d.max(d), false);
        n = d * p10 + offset;
        ops += rops;

        let (n, rops) = reduce_n(n, max_d);

        MEM.with(|mem| mem.borrow_mut().insert((o_n, o_max_d), (n, ops + rops)));
        (n, ops + rops)
    } else {
        (n, 0)
    }
}

fn recurse(n: i64, max_d: i64, first: bool) -> (i64, u64) {
    // println!("descending({}, {})", n, max_d);
    let (o_n, o_max_d) = (n, max_d);
    if n < 10 {
        // println!("0recurse({}, {}) = ({}, {})", o_n, o_max_d, n as i64 - n.max(max_d) as i64, 1);
        return (n - n.max(max_d), 1);
    }
    if max_d == 9 {
        let ops = n / 9 + 1;
        // println!(
        //     "9recurse({}, {}) = ({}, {})",
        //     o_n,
        //     o_max_d,
        //     n as i64 - ops as i64 * 9,
        //     ops
        // );
        return (n - ops * 9, ops as u64);
    }

    if let Some(res) = MEM.with(|mem| mem.borrow().get(&(n, max_d)).copied()) {
        return res;
    }

    // let mut n = n;
    // let mut ops = 0;
    // while n > 0 {
    //     // Remove the largest digit
    //     // let d = digits(n).max().unwrap();
    //     // n -= d;
    //     // ops += 1;
    //     // println!("before next iteration: {} {}", n, ops);
    //     let p10 = pow10(log10(n));
    //     let d = n / p10;
    //     let (offset, rops) = recurse(n - d * p10, max_d.max(d), false);
    //     n = d * p10 + offset;
    //     ops += rops;
    //     if first {
    //         println!("{}", n);
    //     }
    // }
    let (n, ops) = reduce_n(n, max_d);
    // println!(" recurse({}, {}) = ({}, {})", o_n, o_max_d, n, ops);
    // assert_eq!(ops, greedy_f_brute_2(o_n, o_max_d));

    MEM.with(|mem| mem.borrow_mut().insert((o_n, o_max_d), (n, ops)));
    (n, ops)
}

fn f(n: u64) -> u64 {
    if n == 0 {
        return 0;
    }
    let (n, ops) = recurse(n as i64, 0, true);
    assert_eq!(n, 0);
    ops
}

fn solve_brute(x: u64) -> u64 {
    for n in 0.. {
        if f(n) == x {
            return n;
        }
    }
    unreachable!()
}

fn solve(x: u64) -> u64 {
    let mut min = x;
    let mut max = (10 * x).min(i64::MAX as u64);
    while min < max {
        let mid = (min + max) / 2;
        // println!("Testing {}", mid);
        if f(mid) >= x {
            max = mid;
        } else {
            min = mid + 1;
        }
    }
    assert_eq!(f(min), x);
    min
}

fn main() {
    // for d in 1..=9 {
    //     println!("{:?}", recurse(12345, d));
    // }

    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();

    // let mut keys: Vec<Vec<_>> = Vec::new();

    let t: usize = lines.next().unwrap().unwrap().parse().unwrap();
    for _ in 0..t {
        let x: u64 = lines.next().unwrap().unwrap().parse().unwrap();

        // unsafe { MEM = Some(Default::default()) };
        // println!("{}", unsafe { MEM.as_ref().unwrap().len() });
        println!("{}", solve(x));
        // println!("{}", unsafe { MEM.as_ref().unwrap().len() });
        // println!("{:#?}", unsafe { MEM.as_ref().unwrap() });
        // keys.push(unsafe { MEM.as_ref().unwrap().keys().copied().collect() });
    }

    // let keys: Vec<_> = keys.into_iter().map(Vec::into_iter).flatten().collect();
    // let mut counts = HashMap::new();
    // for k in keys {
    //     *counts.entry(k).or_insert(0usize) += 1;
    // }
    // let mut counts: Vec<_> = counts.iter().map(|(k, v)| (*v, *k)).collect();
    // counts.sort();
    // for (c, k) in counts.into_iter().rev().take(1000) {
    //     println!("{} {:?}", c, k);
    // }

    // let n = 9_000_000_000_000_000_000;
    // println!("{:?}", f(n));
    // println!("{:?}", greedy_f_brute(n));

    // MEM.with(|mem| println!("{:#?}", mem.borrow().len()));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn greedy_f_against_brute() {
        let n = 10_000;
        assert_eq!(
            brute_f_until(n),
            (0..=n).map(|i| greedy_f_brute(i)).collect::<Vec<_>>()
        );
    }

    #[test]
    fn greedy_f_against_brute_big() {
        let min = 1_000_000;
        let n = 100;
        let brute = brute_f_until(min + n);
        let greedy: Vec<_> = (min..=min + n).map(|i| greedy_f_brute(i)).collect();
        assert_eq!(&brute[min as usize..], &greedy[..]);
    }

    #[test]
    fn f_against_brute_small() {
        let n = 100;
        assert_eq!(brute_f_until(n), (0..=n).map(|i| f(i)).collect::<Vec<_>>());
    }

    #[test]
    fn f_against_brute() {
        let n = 10_000;
        assert_eq!(brute_f_until(n), (0..=n).map(|i| f(i)).collect::<Vec<_>>());
        // todo!()
    }

    #[test]
    fn f_against_brute_big() {
        let min = 1_000_000;
        let n = 100;
        let brute = brute_f_until(min + n);
        let greedy: Vec<_> = (min..=min + n).map(|i| f(i)).collect();
        assert_eq!(&brute[min as usize..], &greedy[..]);
        // todo!()
    }

    #[test]
    fn test_samples() {
        assert_eq!(solve(1), 1);
        assert_eq!(solve(2), 10);
        assert_eq!(solve(3), 11);
        assert_eq!(solve(4), 20);
        assert_eq!(solve(5), 22);
    }

    #[test]
    fn test_f_samples() {
        assert_eq!(f(1), 1);
        assert_eq!(f(10), 2);
        assert_eq!(f(11), 3);
        assert_eq!(f(20), 4);
        assert_eq!(f(22), 5);

        assert_eq!(f(1 - 1), 1 - 1);
        assert_eq!(f(10 - 1), 2 - 1);
        assert_eq!(f(11 - 1), 3 - 1);
        assert_eq!(f(20 - 1), 4 - 1);
        assert_eq!(f(22 - 1), 5 - 1);
    }

    #[test]
    fn test_brute() {
        for x in 0..=1000 {
            assert_eq!(solve(x), solve_brute(x));
        }
    }

    #[test]
    fn test_large() {
        assert_eq!(solve(1000000000000000000), 8810943982979038346);
        assert_eq!(f(8810943982979038346), 1000000000000000000);
        assert_eq!(f(8810943982979038346 - 1), 1000000000000000000 - 1);
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED