Task: | Numerot |
Sender: | Hennkka |
Submission time: | 2020-10-17 00:22:14 +0300 |
Language: | Rust |
Status: | READY |
Result: | 25 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 13 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.13 s | 2, 3 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3 | details |
Compiler report
warning: unnecessary parentheses around assigned value --> input/code.rs:136:13 | 136 | n = ((d * p10) as i64 + offset); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove these parentheses | = note: `#[warn(unused_parens)]` 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:154:4 | 154 | fn solve_b...
Code
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();}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) = MEM.with(|mem| mem.borrow().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) as i64 + offset);ops += rops;}// 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 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() {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().keys()));}#[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: TIME LIMIT EXCEEDED
input |
---|
1000 627887018110416188 785474884983906653 653772166720939773 784335285960673683 ... |
correct output |
---|
5530371754830260284 6918696171534226533 5757755627065159149 6908439780325129803 3223801064342340738 ... |
user output |
---|
(empty) |