# AtCoder ABC336 Contest

## Overview

- Well well - After having spent a whole week on graphs as I got stuck on ABC 335 - Task E, it turns out that this week’s contest was not really about data structures, but mostly about maths!
- I answered fairly confidently the first three questions - got stuck on the fourth one.

## Task A and B

## Task C - Even Digits

### Objective

Let a “good integer” be an integer written only with 0, 2, 4, 6, 8, i.e. even digits.
The first of such “good integer” is 0, then 2, 4, 6, 8. `10`

is out because it contains a `1`

, so after `8`

we jump straight to `20`

.

The question is, given an integer `N`

, to find the `N`

th “good integer”.

### Algorithm

The brute force algorithm is looking at all integers, testing if they are a “good number” and finding the Nth one.
We won’t go very far because `N`

can be pretty big. (`10^12`

max - that’s a lot).

So ideally we need to find a formula to compute the Nth “good integer”.
Looking at the patterns, we can see that `[0, 2, 4, 6, 8]`

is pretty similar to `0, 20, 40, 60, 80`

and `0, 200, 400, 600, 800`

.
So I noticed that writing the Nth “good number” was equivalent to writing N in base 5, where each symbol is actually [0,2,4,6,8] multiplied by the corresponding powers of 10.

So my algorithm is first to find the “digits” in the base-5 decomposition of N. Then, for each digit, to add 2*the corresponding power of 10.

The code is the following:

```
let mut digits_5: Vec<u8> = vec![];
// The key is to substract 1 from n now!!!
let mut res = n-1;
while res != 0 {
digits_5.push((res % 5) as u8 );
res /= 5;
}
// Now we need to rebuild the number
let mut ans: usize = 0;
for i in 0..digits_5.len() {
ans += 2*(digits_5[i] as usize)*((10 as usize).pow(i as u32));
}
println!("{}", ans );
```

My corresponding submission is here