Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2692
Dialing Dice

Time Limit: 2 Seconds      Memory Limit: 65536 KB

In a certain gambling town, dice have become so popular that they are even used to dial phone numbers. Each face of a six-faced die has a single digit printed on it. The dialing process works as follows. Given a phone number, which is simply a string of digits, one dials the first digit of the number by placing the die on the dialing board. The digit on the bottom face of the die is automatically dialed. To dial the next digit, the die is turned over so that one of the adjacent sides is now on the bottom. Again the digit on the new bottom face is dialed. The procedure continues until all the digits of the target phone number are dialed.

Unfortunately, as you might imagine, there are quite a few problems with this dialing method. First, the standard dice (with faces labeled 1 through 6) are not capable of dialing certain crucial numbers such as 911. To remedy this situation, people were allowed to "program" their dice by choosing any digits to place on the faces (two faces may contain the same digit).

As it turns out, this remedy still does not fully solve the problem, since no die can dial 1234567 (there are 7 digits, but only 6 sides on a die). When this was discovered, the people threw up their hands along with their dice and went back to their gambling. A few days of mulling over the problem lead to a new solution: people would be only required to dial a number that has small discrepancy with respect to the number that they really want to dial. The discrep- ancy between the two numbers is the minimum number of additions, deletions, or substitutions of digits required to transform one num- ber into the other. For example, the discrepancy between 91 and 911 is 1, between 12399 and 1499 is 2, etc.

People often wondered about the optimal way to program their dice. Your task is to write a program to help them out. Given a target number N, program a die so that the die can be used to dial some number N0, where the discrepancy between N and N0 is minimized. Note that the die can be programed with any digits, regardless of the target phone number.

(You might notice other di��culties with this dialing system, but those are to be solved in a future task.)


Each line of the input contains exactly one phone number of length 1 <= N <= 100. While the number may contain any digits from 0 to 9, a given number contains at most 7 distinct digits.


For each number, output the minimum discrepancy that can be ob- tained by any die and the 6 digits on the die that achieves that discrepancy. Sort the digits in ascending order. If there are ties, print out the sequence of digits that is lexicographically smallest.

Sample Input


Sample Output

Dice 1: discrepancy is 0, digits used: 0 0 0 0 0 0
Dice 2: discrepancy is 0, digits used: 0 0 1 1 2 2
Dice 3: discrepancy is 1, digits used: 1 2 3 3 4 5

Source: MIT Programming Contest, 2005.02.26
Submit    Status