Numerot

warning: unused import: `std::cell::RefCell`
 --> input/code.rs:1:5
  |
1 | use std::cell::RefCell;
  |     ^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

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

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

warning: function is never used: `greedy_f_brute`
  --> input/code.rs:45:4
   |
45 | fn greedy_f_brute(n: u64) -> u64 {
   |    ^^^^^^^^^^^^^^

warning: function is never used: `greedy_f_brute_2`
  --> input/code.rs:55:4
   |
55 | fn greedy_f_brute_2(n: u64, max_d: u64) -> u64 {
   |    ^^^^^^^^^^^^^^^^

warning: function is never used: `solve_brute`
   --> input/code.rs:160:4
    |
160 | fn solve_brute(x: u64) -> u64 {
    |    ^^^^^^^^^^^

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

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: u64) -> u64 {
    if n <= 9 {
        0
    } else {
        1 + log10(n / 10)
    }
}

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

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

static mut MEM: Option<HashMap<(u64, u64), (i64, u64)>> = None;

fn recurse(n: u64, max_d: u64) -> (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 as i64 - n.max(max_d) as i64, 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 as i64 - ops as i64 * 9, ops);
    }

    if let Some(res) = unsafe { MEM.as_ref().unwrap().get(&(n, max_d)).copied() } {
        return res;
    }

    let mut n = n as i64;
    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 as u64)) as i64;
        let d = n / p10;
        let (offset, rops) = recurse((n - d * p10) as u64, max_d.max(d as u64));
        n = d * p10 + offset;
        ops += rops;
    }
    // println!(" recurse({}, {}) = ({}, {})", o_n, o_max_d, n, ops);
    // assert_eq!(ops, greedy_f_brute_2(o_n, o_max_d));
    unsafe {
        MEM.as_mut()
            .unwrap()
            .insert((o_n as u64, o_max_d), (n, ops));
    }
    (n, ops)
}

fn f(n: u64) -> u64 {
    if n == 0 {
        return 0;
    }
    let (n, ops) = recurse(n, 0);
    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 = 0;
    let mut max = i64::MAX as u64;
    while min < max {
        let mid = (min + max) / 2;
        if f(mid) >= x {
            max = mid;
        } else {
            min = mid + 1;
        }
    }
    min
}

fn main() {
    unsafe { MEM = Some(Default::default()) };
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();

    let t: usize = lines.next().unwrap().unwrap().parse().unwrap();
    for _ in 0..t {
        let x: u64 = lines.next().unwrap().unwrap().parse().unwrap();
        println!("{}", solve(x));
    }

    // 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: TIME LIMIT EXCEEDED