Problem Definition

You are to initially assume that you have 1-dimensional array full of null values. The input will specify a positive integer value, say n (3 <= n <= 100), followed by exactly 3 x n counts of space-separated positive integer values that mention a list of operations. The 3 x n integers can be generalised to follow a periodic pattern of a b k for a period of 3. Each triplet has to be used to calculate exactly k number of values. Each of the k values have to be calculated by the equation

c_i = a^2 + (b * (-1)^i ) ∀ i | 1 <= i <= k … (1)

Starting with the 1-dimensional array full of null values, process each triplet and compute the operations to calculate the corresponding set of values. For each triplet, compute the set of k values and overwrite them sequentially in to the 1-dimensional array starting at index a and ending at index b. Array indices can be assumed to start at 0 and end at t-1 for an array of size t. If k values are not sufficient to fill indices between a and b, then fill the initial k indices starting from a alone leaving the values in the remaining cells as such. If k values exceed indices between a and b, do not let them overflow.

For each of the n triplets in the input, compute the set of k values and insert them in to the 1-dimensional array starting at index a and ending at index b overwriting previous values in the k locations previously in array.

Once all operations have been performed, return the largest value in the array.

Input Format:

First line of input will be an integer value. Next line will be exactly 3 * n counts of space-separated integer values.

An integer value n followed by exactly 3xn space-separated integer values

Conditions

n will be integer value in the interval 3 <= n <= 100

For each of the subsequent triplets a b k

0 <= a <= b <= 100

0 <= k <= 20

Output Format:

Exactly 1 integer value (largest among the generated values) followed by a newline

In case of any constraint violation the program should terminate printing a newline.

Sample Input 0

10

1 5 3 4 8 2 6 9 1 2 5 2 1 9 7 8 8 1 1 5 5 8 9 2 6 9 0 2 6 4

Sample Output 0

73

Sample Input 1

5

1 13 7 11 13 8 11 15 1 11 15 6 0 5 5

Sample Output 1

136

Sample Input 2

12

1 13 7 11 13 8 11 15 1 11 15 6 0 5 5

Sample Output 2

Programming Requirements:

• Object-oriented programming
• Dynamic arrays or lists

Example 1

10 <= n

1 5 3 4 8 2 6 9 1 2 5 2 1 9 7 8 8 1 1 5 5 8 9 2 6 9 0 2 6 4 <= list of operations

The list of operations can be interpreted as:

a       b       k

1       5       3

4       8       2

6       9       1

2       5       2

1       9       7

8       8       1

1       5       5

8       9       2

6       9       0

2       6       4

For first triplet, say n=1, a=1, b=5, k=3, overwrite k values computed by equation 1 at the indices starting from a until b mentioned as follows:

C1 = 1x1 + (-1)^1 x 5 => C1 = 1 + -5 => C1 = -4

C2 = 1x1 + (-1)^2 x 5 => C2 = 1 + 5 => C2 = 6

C3 = 1x1 + (-1)^3 x 5 => C3 = 1 + -5 => C3 = -4

n       a       b       k       index=>       0       1       2       3       4       5       6       7       8       9       10

0       -       -       -                             0       0       0       0       0       0       0       0       0       0       0

1       1       5       3                            0       -4       6       -4       0       0       0       0       0       0       0

2       4       8       2                            0       -4       6       -4       8       24       0       0       0       0       0

3       6       9       1                            0       -4       6       -4       8       24       27       0       0       0       0

4       2       5       2                            0       -4       -1       9       8       24       27       0       0       0       0

5       1       9       7                            0       -8       10       -8       10       -8       10       -8       0       0       0

6       8       8       1                            0       -8       10       -8       10       -8       10       -8       56       0       0

7       1       5       5                            0       -4       6       -4       6       -4       10       -8       56       0       0

8       8       9       2                            0       -4       6       -4       6       -4       10       -8       55       73       0

9       6       9       0                            0       -4       6       -4       6       -4       10       -8       55       73       0

10       2       6       4                            0       -4       -2       10       -2       10       10       -8       55       73       0

Indices of array are ONLY relevant and applicable to current input scenario and MUST NOT be assumed to be consistent for all test cases or associated with n blindly.

The largest value after performing all operations is 73.

TAGS: Linear Data Structures