CodeSprintLA 2020 — Team Competition

Start

2020-05-23 09:30 AKDT

CodeSprintLA 2020 — Team Competition

End

2020-05-23 12:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -392 days 19:18:43

Time elapsed

2:30:00

Time remaining

0:00:00

Problem E
Heather Code

/problems/codesprintla20.heathercode/file/statement/en/img-0001.jpg
January 26, 2020. Photo by osseous

Heather Grey has decided she would like to unlock the combination lock that USC has used to lock up Tommy Trojan before the UCLA versus USC football game.

The multi-ring combination lock has $7$ rings on it. Each ring has the 10 digits $0,1,2,\dots 9$ printed on it in that order. One row of the lock represents the code. Initially, the code entered is $0000000$. Heather wants to crack the lock, so she needs to try every possible digit combination. The rings must be turned one digit at a time and can only be turned in one direction, so that it takes one turn to get from $0$ to $1$, one turn to get from $1$ to $2$, and so on, and one turn to get from $9$ to $0$. Heather wants to take the least number of turns possible, so she uses the following procedure: every second, she chooses a ring and moves it by one turn, such that she always chooses the rightmost ring that will not cause her to try a code she’s already tried. (If it’s impossible for her to choose such a ring, she stops.)

Here is a table of the codes Heather tries for $n$ turns, with $0 \leq n \leq 20$:

$\begin{array}{l|l} 0 & 0000000\\ 1 & 0000001\\ 2 & 0000002\\ 3 & 0000003\\ 4 & 0000004\\ 5 & 0000005\\ 6 & 0000006\\ 7 & 0000007\\ 8 & 0000008\\ 9 & 0000009\\ 10 & 0000019\\ 11 & 0000010\\ 12 & 0000011\\ 13 & 0000012\\ 14 & 0000013\\ 15 & 0000014\\ 16 & 0000015\\ 17 & 0000016\\ 18 & 0000017\\ 19 & 0000018\\ 20 & 0000028 \end{array}$

Input

The only line of the input contains the integer ($1 \leq n \leq 9\, 999\, 999$).

Output

Print $7$ digits representing the code that Heather tries on her $n$th turn. It is guaranteed that Heather will make at least $n$ turns.

Sample Input 1 Sample Output 1
1
0000001
Sample Input 2 Sample Output 2
10
0000019
Sample Input 3 Sample Output 3
20
0000028
Sample Input 4 Sample Output 4
100
0000190
Sample Input 5 Sample Output 5
9999999
9000000