|
G |
SMS
for Blinds Input: Standard Input Output: Standard Output |
|
Almost all the devices we use are designed for normal people and in most cases those who are not normal adapt to these devices and we praise them a lot for their brilliance. But for disabled people this might not be that pleasant Imagine that we are living in the land of cockroaches and we have to walk on the walls by wearing super glue shoes because their roads and bridges are designed in that way.
|
|
|
|
Figure 1: Draft design of a Normal Mobile Phone |
Figure 2: Draft design of a mobile phone designed for blind people |
So IBM (International Business Mobile) has designed a new set for blind people that have only one large button for typing characters and three other buttons for sending or receiving phones and changing input modes. As there is only one button for typing SMS, therefore one might need to press a button up to 26 times to type a character. So the designers have omitted some characters: for example k is replaced with c, to reduce the total number of alphabets to 19 (including white space which for simplicity is denoted by the character underscore (_). The following table shows which characters are replaced by what:
|
a
b c d e f g h I g c c b u cs i g _ |
|
Figure: the characters j, k, q, v, w, x, y , z are written using other characters. So the reduced alphabet size becomes 18. So SMS message contain only these 18 different characters and also white space which is denoted with _ underscore. So all the SMS messages contain total 19 different characters |
The order in which the characters are written on the large button denotes how many pushes are required to type a character. Lets term this ordering as KEY ORDER. For example if the characters are written in order "_abcdilefmnoprghstu", then to type c four presses are required, to type r 14 presses are required and so on. And to type abacus total (2+3+2+4+19+17) = 47 presses are required. Given the KEY ORDER and the SMS to type it is very easy to find out the total number of presses to type that message. But in this problem you will be given the SMS to be typed and total number of presses needed to type that SMS. From this information you will have to find the KEY ORDER.
Input
The input file contains total 1200 sets of inputs. The description of each set is given below:
First line of the input for each set contains a string, which is the SMS to be typed. This string contains only 19 different characters and has a maximum length 1000. The next line contains an integer C which denotes the total number of presses to type that string. The characters in the string are mostly randomly generated. But this string can only contain characters present in the string "_abcdefghilmnoprstu".
Input is terminated by a line containing a single *.
Output
For each set of input produce one line of output. This line contains a string which denotes the KEY ORDER that will ensure that the typing cost of the given SMS message is equal to C. If there is more that one possible ordering, any one will do. There will be no such input for which a ordering is not found and this string should contain exactly 19 characters (only allowed characters are the characters in the string "_abcdefghilmnoprstu") and these characters should be different (No character should be present twice). Note that it may be heard to find a strategy that funds solution for all possible inputs, so if your output formatting is right (String length 19 and all characters different and from the string "_abcdefghilmnoprstu") but your cost is wrong for at most 10 cases (of the 1200 cases), then your solution will be accepted.
Sample Input Output for
Sample Input
|
tsnobfsr_emlllla_dtuangtcrhgpguthngrff 366 aausuufoisuflhdeihdauhnhiatlcusion 353 o_nmhfulhfmihl_febdiaommff_ 304 * |
grudefpin_hbtamsclo uperbtsaclf_gdonhmi hsugtrd_pibfnolaemc |
Problemsetter: Shahriar Manzoor
Some Suggestions: Derek Kisman