Connection Status:
Competition Arena > RLESum

RLESum

TCCC07 Sponsor 2 · 2007-07-30 · by andrewzta

TCCC07 Sponsor 2 · 2007-07-30 · by andrewzta · Math
Class Name: RLESum
Return Type: int[]
Method Name: getDigits
Arg Types: (string, string, vector<string>)
Problem Statement

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.

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.

3)
"[1000000000000000000]1"
"[1000000000000000000]9"
{"1000000000000000000", "0"}
Returns: {1, 0 }
4)
"[1000000000000000000]1"
"[1000000000000000000]1"
{"999999999999999999"}
Returns: {2 }

Submissions are judged against all 226 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RLESum with a public method vector<int> getDigits(string a, string b, vector<string> k) · 226 test cases · 2 s / 256 MB per case

Submitting as anonymous