Problem C
Ignore the Garbage

Fred works as an IT consultant in an insurance company. As they always had a large amount of customers waiting and arguing at the front desk, management decided to deploy a ticket machine. Each customer would get a ticket with a number and there will be fancy LCD display over each desk showing the number of the next person. Fred was appointed to get this new enhancement working.

Because Fred is lazy when it comes to manual labor and as an IT consultant he wouldn’t lower himself to the level of some hardware technician (except when upgrading his own computer), he asked few technicians to install the displays and prepared himself just to plug in the ticket machine and try it out. Unfortunately (for Fred) the technicians, either inspired by Mr.Bean or because of their carelessness, installed the display upside-down.

Being a software guy, Fred decided that the hardware should not be tampered with after it is installed (except for the case if he would be able to get back the technicians to repair it, but they were already angry at him for his nagging). Then he noted that from time to time the display shows a correct number even when it is upside-down. And hey, the ticket machine is an embedded device and contains a small processor! It would be just a sin for an IT guy not to try to meddle with it and try running an own version of Linux. Now we just need to figure out which readable numbers will the display show.


In the beginning the display shows the number 1 on its display. Each second the number shown is increased by 1. We see the display upside-down and thus not everything we see will make sense. Your task is to compute the $K$-th valid number we will see on the display. The digits the display uses are shown on the images below. An upside-down 1 still count as 1. The number we see may have leading zeroes – e.g. turning the number 600 upside down leads to a valid number.

\includegraphics[width=1cm]{i0.png} \includegraphics[width=1cm]{i1.png} \includegraphics[width=1cm]{i2.png} \includegraphics[width=1cm]{i3.png} \includegraphics[width=1cm]{i4.png} \includegraphics[width=1cm]{i5.png} \includegraphics[width=1cm]{i6.png} \includegraphics[width=1cm]{i7.png} \includegraphics[width=1cm]{i8.png} \includegraphics[width=1cm]{i9.png}


Input file will consist of several integers $K_ i$, one per line. There will be at most 1100 lines in the input.


For each $K_ i$ from the input file, output the $K_ i$-th number shown on the display (including the leading zeroes, if there are some).

Sample Input 1 Sample Output 1
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Michal Forišek and Jozef Šiška
Source IPSC 2005
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in