Problem Statement

Inmates on planet Elba II are making license plates for the various departments of interplanetary vehicles of the Federation. All plates denote positive numbers using the digits '0'-'9'. No plate ever contains a leading 0.

Unfortunately, certain pairs of digits are considered obscene by different planets. Therefore, no plate can be created that contains those adjacent sequences of digits.

The plates are ordered by the value of the positive number on them. They are then numbered by their placement on that ordered list; this numbering is called the sequence number. Thus, the plate with sequence number 1 has "1" on it, the plate with sequence number 9 has "9" on it, and beyond that, the plates are determined by what digit pairs are legal. For instance, if only the digit sequence "10" was illegal, then the plate with sequence number 10 would be "11", and the plate with sequence digit 99 would be "111".

Your task as a lowly programmer peon on Elba II is to write a method to determine the plate number, given the set of digit pairs that are illegal and the sequence number of the plate. If there can be no plate with that sequence number, return the empty string.

If the plate has more than 50 digits, only return the first 47 digits followed by "..." (quotes for clarity).

The illegal digits will be given in the String[] profane. Each element of profane will contain a sequence of digit pairs, separated by spaces.

Definition

 Class: ValidPlates Method: getPlate Parameters: String[], int Returns: String Method signature: String getPlate(String[] profane, int seqno) (be sure your method is public)

Constraints

-seqno will be between 1 and 2,000,000,000, inclusive.
-profane will contain between 0 and 50 elements, inclusive.
-Each element of profane will contain between 2 and 50 characters, in the format described above.
-Each element of profane will contain only spaces and digits ('0'-'9').
-Each element of profane will consist of a sequence of digit pairs separated by single spaces, with no leading or trailing spaces.

Examples

0)

 `{}` `1000`
`Returns: "1000"`
 With no restrictions, the 1000th plate is simply "1000".
1)

 `{"10"}` `10`
`Returns: "11"`
 If the digit sequence "10" is not allowed, the 10th plate must be 11.
2)

 `{"10"}` `2000000000`
`Returns: "2277659869"`
3)

 ```{"00 01 02 03 04 05 06 07 08 09 11 12 13 14 15 16 17", "18 19 22 23 24 25 26 27 28 29 33 34 35 36 37 38 39", "44 45 46 47 48 49 55 56 57 58 59 66 67 68 69 77 78", "79 88 89 99 99 99 99 99"}``` `1023`
`Returns: ""`
 Disallowing any digit pair where the digits do not decrease only permits a total of 1022 plates. Note that profane may contain duplicate elements.
4)

 ```{"00 01 02 03 04 05 07 08 09", "10 11 12 13 14 15 17 18 19", "20 21 22 24 25 26 27 28 29", "30 31 32 33 34 36 37 38 39", "41 43 45 46 48", "52 53 54 55 56 58 59", "60 61 63 64 66 67 68 69", "70 72 73 74 75 76 77 78", "80 81 82 83 84 86 87 88 89", "90 91 92 94 95 96 97 98"}``` `2000000000`
`Returns: "79999999351623516571657999935799993"`
5)

 ```{"00 01 02 03 04 05 06 07 08 09", "10 11 12 13 14 16 17 19", "20 21 22 23 24 25 26 27 28 29", "30 31 32 33 34 35 36 38 39", "41 42 43 44 45 46 49", "50 52 53 54 55 57 58 59", "60 61 62 63 64 65 66 67 68 69", "70 72 73 74 75 76 77 78 79", "80 81 82 83 84 85 86 87 88 89", "90 91 92 93 94 95 98 99"}``` `2000000000`
`Returns: "37151515151515151515151515151515151515151515151..."`
 The final plate has 166,666,668 digits.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6876

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10665&pm=6876