Task: | Numerot |
Sender: | Hennkka |
Submission time: | 2020-10-17 01:30:18 +0300 |
Language: | Rust |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 13 |
#3 | ACCEPTED | 75 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.05 s | 2, 3 | details |
#3 | ACCEPTED | 0.31 s | 3 | details |
Compiler report
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...
Code
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 details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1000 1 2 3 4 ... |
correct output |
---|
1 10 11 20 22 ... |
user output |
---|
1 10 11 20 22 ... Truncated |
Test 2
Group: 2, 3
Verdict: ACCEPTED
input |
---|
1000 224995 413660 249827 2125 ... |
correct output |
---|
1731724 3216040 1940719 14585 532612 ... |
user output |
---|
1731724 3216040 1940719 14585 532612 ... Truncated |
Test 3
Group: 3
Verdict: ACCEPTED
input |
---|
1000 627887018110416188 785474884983906653 653772166720939773 784335285960673683 ... |
correct output |
---|
5530371754830260284 6918696171534226533 5757755627065159149 6908439780325129803 3223801064342340738 ... |
user output |
---|
5530371754830260284 6918696171534226533 5757755627065159149 6908439780325129803 3223801064 ... Truncated |