Problem Statement
You are given three numbers: a, b, and c. You need to generate three arrays A, B, C of lengths a, b, c using the pseudocode given below:
A[0] = 33
A[1] = 42
for i = 2 to a-1:
A[i] = (5*A[i-1] + 7*A[i-2]) modulo 1000000007 + 1
B[0] = 13
for i = 1 to b-1:
B[i] = (11*B[i-1]) modulo 1000000007 + 1
C[0] = 7
C[1] = 2
for i = 2 to c-1:
C[i] = (5*C[i-1] + 7*C[i-2]) modulo 1000000007 + 1
Now that you have 3 arrays A , B and C, you can perform three types of moves:
- Remove one element each from arrays A and B. The cost of this operation is (x + the sum of elements you removed).
- Remove one element each from arrays B and C. The cost of this operation is (y + the sum of elements you removed).
- Remove one element each from arrays A and C. The cost of this operation is (z + the sum of elements you removed).
You need to minimize the sum of elements remaining in these arrays after performing above mentioned operations any number of times. If there are multiple ways to obtain the minimum sum, you need to minimize the cost of doing so.
Return an array of two integers containing the minimum sum (at index 0) and minimum cost of obtaining the minimum sum (at index 1).
Definition
- Class:
- DeleteArrays
- Method:
- doDelete
- Parameters:
- int, int, int, long, long, long
- Returns:
- long[]
- Method signature:
- long[] doDelete(int a, int b, int c, long x, long y, long z)
- (be sure your method is public)
Notes
- The input format is only chosen to keep the input size small. The reference solution does not depend on any properties of these arrays A, B, C, it would work correctly for any arrays of the given length.
- Watch out for integer overflows, both when generating the input arrays and when calculating the return values.
- The elements of arrays can be removed in any order.
Constraints
- Each of a, b and c will be between 2 and 10^5, inclusive.
- Each of x, y and z will be between 1 and 10^9, inclusive.
Examples
2
2
2
2
3
4
Returns: {0, 250 }
The arrays are: A = {33, 42} B = {13, 144} C = {7, 2} We can remove first elements from arrays A and B with cost (2 + 33 + 13) = 48. Next we remove the remaining element from A and the first element of C with cost (4 + 42 + 7) = 53. Finally, we remove the remaining elements from B and C with cost (3 + 144 + 2) = 149. Sum of Elements remaining = 0, which is clearly optimal. Cost = 48 + 53 + 149 = 250.
3
2
2
3
2
1
Returns: {2, 688 }
The arrays are: A = {33, 42, 442} B = {13, 144} C = {7, 2} One optimal solution: Remove 33 from A and 13 from B, cost = (3 + 33 + 13) = 49. Remove 442 from A and 144 from B, cost = (3 + 442 + 144) = 589. Remove 42 from A and 7 from C, cost = (1 + 42 + 7) = 50. Sum of remaining elements = 2. Total cost = 49 + 589 + 50 = 688.
24561
4357
3117
3895
2425
11697
Returns: {6002652266123, 10041603080088 }
340
500
234
1
1
1
Returns: {0, 498124880075 }
1000
100
100
2352
232
4263
Returns: {320467404289, 272083126790 }
100000
100000
100000
1000000000
1000000000
1000000000
Returns: {0, 300032828081557 }
99322
53825
63242
5249892
549867389
9487287
Returns: {2, 113894579390551 }
93752
49372
74872
728742
8749352
627486
Returns: {0, 109284966700308 }
378
739
273
7283948
7362920
22445294
Returns: {3714137346, 651760769179 }
12345
23456
90000
12345678
87654321
45637218
Returns: {16221250253396, 49158247658663 }
24919
92482
89398
12472845
5236184
86759274
Returns: {2, 104876254624144 }
5
3
3
100
150
20
Returns: {2, 20791 }
38
19
31
52
91
62
Returns: {0, 30906467879 }
2
2
2
1
1
1
Returns: {0, 244 }
50
89
44
83
93
11
Returns: {2, 75713874770 }
99999
89999
79999
99999999
91199199
89989881
Returns: {2, 147715135375367 }
100000
60000
50000
1938498
8492872
4264828
Returns: {0, 105389599284314 }
100
101
99
827674
783872
278428
Returns: {0, 131939888876 }
12345
36848
94653
444555
899898
135368
Returns: {10841879505385, 61002687704512 }
9191
8383
7274
8284273
9342716
2639721
Returns: {0, 12485722058342 }
2322
34452
34452
100000000
100000000
100000000
Returns: {0, 39089160480679 }
4
4
4
5
6
7
Returns: {0, 22620 }
100000
5
8
424242
474747
123456789
Returns: {50097960828195, 13989929548 }
66666
77777
100000
424242
474747
123456789
Returns: {2, 127728060944833 }
43
76
84
92
65
98
Returns: {2, 88999667633 }
19
86
43
51
45
20
Returns: {2647784842, 58609762349 }
10000
10000
10000
1
1
1
Returns: {0, 14993564220213 }
8
2
2
2
2
2
Returns: {3022, 4306009 }
17
43
8
76
65
36
Returns: {2329630862, 23590119930 }