Hide

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
CPU Time limit 1 second
Memory limit 1024 MB
Author
Jacob Zhang
Source CodeSprintLA 2020 (UCLA ACM-ICPC)
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in