CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Numerot
Sender:Hennkka
Submission time:2020-10-17 00:22:14 +0300
Language:Rust
Status:READY
Result:25
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED13
#30
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2, 3details
#2ACCEPTED0.13 s2, 3details
#3--3details

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:

input
1000
627887018110416188
785474884983906653
653772166720939773
784335285960673683
...

correct output
5530371754830260284
6918696171534226533
5757755627065159149
6908439780325129803
3223801064342340738
...

user output
(empty)