TopCoder problem "RLESum" used in TCCC07 Round 2 (Division I Level Two)



Problem Statement

    

An RLE compressed number is uncompressed as follows. Replace each occurrence of the substring "[k]c" (quotes for clarity), where k is a positive integer without leading zeroes and c is a single digit, with k consecutive occurrences of c. For example, "12[3]3[2]4[5]1" uncompresses to "123334411111". "123[2]3441[3]11" uncompresses to the same number.

Note that uncompression is not recursive; brackets are not allowed to be nested.

You are given two RLE compressed numbers a and b and String[] k. Uncompress a and b, and add them together. Return a int[], the i-th element of which is the k[i]-th digit of the sum. The 0-th digit is the rightmost digit, the 1-st digit is the next digit to the left, etc. If there are not enough digits, the corresponding element must be equal to 0.

 

Definition

    
Class:RLESum
Method:getDigits
Parameters:String, String, String[]
Returns:int[]
Method signature:int[] getDigits(String a, String b, String[] k)
(be sure your method is public)
    
 

Constraints

-a and b will contain only digits ('0'-'9') and brackets ('[' and ']').
-a and b will each contain between 1 and 50 characters, inclusive.
-a and b will each be an RLE compressed number that uncompresses to a valid positive integer with no extra leading zeroes.
-a and b, when uncompressed, will each contain no more than 10^18 digits.
-k will contain between 1 and 50 elements, inclusive.
-Each element of k will be an integer between 0 and 10^18, inclusive, without extra leading zeroes.
 

Examples

0)
    
"[12]3"
"[3]1[3]2[3]3"
{"12", "11", "10", "9", "8","7","6","5","4","3","2","1","0"}
Returns: {0, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6 }
a decompresses to 333333333333, and b decompresses to 111222333. Their sum is 333444555666. We return all of its digits, and also 0 for the 12-th digit which doesn't exist.
1)
    
"[5]9"
"[5]9"
{"5", "0", "1"}
Returns: {1, 8, 9 }
2)
    
"123456789"
"987656789"
{"10", "9", "1", "3", "1", "2"}
Returns: {0, 1, 7, 3, 7, 5 }
Note that k need not be sorted, and its elements can be equal to each other.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10891&pm=8111

Writer:

andrewzta

Testers:

PabloGilberto , radeye , Olexiy , ivan_metelsky

Problem categories:

Math