Problem C
The Integer All-time Champ
Input: standard input
Output: standard output
Time Limit: 30 seconds
As Alan Turing and his friend David Champernowne gave the name “The All-time Champ” number (as a joke with the David surname) to the trascendental constant 0.1234567891011... obtained by concatenating the positive integers and interpreting them as decimal digits to the right of a decimal point, let us nominate “All-time Champ Integers” to the numbers constructed by concatenating the digits of a set of consecutive integers.
Given two natural numbers 0<m<=n, there is a such integer, but there are other natural numbers that contain, as substrings, all the numbers between m and n, both included. For example for m=1 and n=13, possible solutions are 12345678910111213 (the corresponding “Champ”), 1011213456789 or 1101213456789. We can see that the last two numbers have only 13 digits as against the 17 of the “Champ”.
Your task is to find out the shortest such integer.
Input
The input file contains several lines of input. Each line contains two natural numbers m and n (0<m<=n<100). Input is terminated by end of file.
Output
For each line of input produce one line of output. This
line contain the shortest integer that contains as substring all the
numbers between m and n (both included). There may be more
than one solution. We will accept any one of the solutions.
Sample Input:
1 13
1 4
13 14
11 12
Sample
Output:
1101213456789
1234
1314
112
(World Final Warm-up
Contest, Problem Setter: Miguel Revilla)