TopCoder problem "ValidPlates" used in SRM 341 (Division I Level Three)



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

Writer:

radeye

Testers:

PabloGilberto , brett1479 , Olexiy , Jan_Kuipers , Andrew_Lazarev

Problem categories:

Dynamic Programming, Geometry, Math