Problem Statement |
| | In this problem, you will be given descriptions of several integer sequences, and you will be required to return elements at certain positions of the union of all the given sequences. The union of several sequences is a sequence containing all the elements of those sequences, sorted in non-decreasing order. For each integer x, the number of occurrences of x in the union is equal to the total number of occurrences of x in all the given sequences. For example, if we are given sequences (3, 2, 2, 3), (1) and (5, 7, 1), their union is the sequence (1, 1, 2, 2, 3, 3, 5, 7).
Each of the given sequences will be an arithmetic sequence, a geometric sequence or an explicit sequence.
-
An arithmetic sequence is described by three positive integers A, B and C. The sequence contains exactly C elements: A, A+B, A+B+B, ..., A+B*(C-1). Formally, the sequence is { A+B*x | x an integer between 0 and C-1, inclusive}.
-
A geometric sequence is described by three positive integers A, B and C. The sequence contains exactly C elements: A, A*B, A*B*B, ..., A*B^(C-1). Formally, the sequence is { A*B^x | x an integer between 0 and C-1, inclusive}.
-
An explicit sequence is just a non-empty sequence of arbitrary positive integers.
Each sequence will be represented as a String, where the first character is 'A', 'G' or 'E', denoting arithmetic, geometric or explicit sequences, respectively. The second character will always be a space. After that is a list of positive integers, where each integer is written with no leading zeroes, consecutive integers are separated by a single space, and there are no leading or trailing spaces. In the case of arithmetic and geometric sequences, this list will always contain exactly three integers, A, B and C, in that order, as described above for each type of sequence. For explicit sequences, the list will contain one or more integers, explicitly representing the members of the sequence.
You will be given a String[] seqs, where each element represents a sequence as described in the previous paragraph, and a int[] positions, which contains a list of 1-based positions. Return a int[] containing the same number of elements as positions, such that its i-th element is the element at position positions[i] of the union of all the sequences in seqs. If the union contains less than positions[i] elements or if the element at position positions[i] of the union is strictly greater than 1000000000 (10^9), the i-th element of the return must be -1 instead. See examples for further clarification. |
| |
Definition |
| | | Class: | SequenceMerger | | Method: | getVal | | Parameters: | String[], int[] | | Returns: | int[] | | Method signature: | int[] getVal(String[] seqs, int[] positions) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The elements of the given sequences don't necessarily fit within 32-bit or 64-bit integer types. |
| |
Constraints |
| - | positions will contain between 1 and 50 elements, inclusive. |
| - | Each element of positions will be between 1 and 1000000000 (10^9), inclusive. |
| - | seqs will contain between 1 and 50 elements, inclusive. |
| - | Each element of seqs will contain between 3 and 50 characters, inclusive. |
| - | Each element of seqs will be formatted as described in the problem statement. |
| |
Examples |
| 0) | |
| | {"E 1 1000000000 1000000001"} | {1,2,3,4} |
| Returns: {1, 1000000000, -1, -1 } | | The sequence here has only 3 elements. The first two elements are returned normally. The element at position 3 is strictly greater than 1000000000, so you must return -1 in that place. There is no element at position 4, so you must also return -1 there. |
|
|
| 1) | |
| | {"A 1 1 10", "G 1 2 4"} | {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} |
| Returns: {1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 10, -1 } | | The arithmetic sequence is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. The geometric sequence is 1, 2, 4, 8. Therefore, the resulting sequence is 1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 10. |
|
|
| 2) | |
| | {"A 1000000000 1000000000 1000000000","G 100000000000000000 1000000000000 100000000000000", "E 1000000000000000 10000000 10 1111"} | {1,2,3,4,5,6,7,8,9,10} |
| Returns: {10, 1111, 10000000, 1000000000, -1, -1, -1, -1, -1, -1 } | | Watch out for big numbers. |
|
|
| 3) | |
| | {"G 1 1 999999999", "E 2"} | {1,999999999,1000000000} |
| Returns: {1, 1, 2 } | |
|
| 4) | |
| | {"A 100 341 1524", "G 1 3 45235", "E 653 87 12341 8785 123 543"} | {100000,1,10,10000,100,1000} |
| Returns: {-1, 1, 441, -1, 28403, 334621 } | |
|