Server Time: Wed Feb 26, 2020 2:10 pm
Welcome ( logout
B - Candles
PDF (English) Ranklist
Time Limit: 3 second(s) Memory Limit: 32 MB

 

b1.jpg

Figure 1: Digit-shaped candles

b2.jpg

Figure 2: A cake with two candles denoting silver jubilee

It is the 68th birthday of Animesh’s father, so he is in “Archies’s Gift Shop” of Banani (A place in Dhaka) to buy candles. He convinces his dumb head that buying 68 candles won’t be such a good idea. But in the shop he finds some digit shaped candles and realizes that if he buys only two candles (One ‘6’ and another ‘8’) he can display his father’s age on the cake. But now he wants to buy digit shaped candles so that he can display ages of all the members of his family during their birthdays. Minimum how many candles does he need to buy? He has to obey the following restrictions:

 

1. There are only 10 pieces of candles in the store. 10 candles have the shape of 10 decimal digits as shown in figure 1. Therefore he can buy at most one candle of each shape. There is another candle at Animesh’s home which has the shape of ‘+’. So he does not need to buy that one.  He can buy all ten digit shaped candles, but he wants to buy minimum number of candles, as for him these candles are not cheap.

 

2. He can only use the digit shaped candles to display an age, but also he can use the ‘+’ shaped candle he already owns to display the age as sum of two numbers. For example if someone is 12 years old, he can display his age as 2+10, 3+9, 4+8, 5+7, 7+5, 8+4, 9+3, 10+2 or 12.

 

Input

The input file contains less than 10000 line of input. Each line starts with an integer n (1 <= n <= 10) which denotes total no of members in Animesh’s family. This integer is followed by n integers, all of which are within the range 1 and 100 (inclusive). These integers denote the ages of the members of Animesh’s family on their very next birthday. A line containing a single zero terminates input. This line should not be processed.

 

Output

For each line of input produce one line of output. This line contains the serial of output followed by some digits, which actually denotes the candles that Animesh must buy so that he can display the age of all his family members on their birthday. These digits are printed in descending order. These digits forms a number, lets call this number T. You can assume that their birthdays are in different dates so same candle can be used in more than one birthday. If there is more than one way to buy minimum number of candles, try to minimize the value of T. Look at the output for sample input for details. You can assume that there will always be a solution.

 

Sample Input                             Output for Sample Input

2 10 11

1 30

0

 

Case 1: 654

Case 2: 30

 


 


Problem Setter: Shahriar Manzoor
Special Thanks: Jane Alam Jan, Sohel Hafiz
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan