Problem Statement
Brus does not know John's array. He only knows n, d, first and last. He wants to compute the maximal possible element John might have in his array.
You are given
Definition
- Class:
- TheArray
- Method:
- find
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int find(int n, int d, int first, int last)
- (be sure your method is public)
Notes
- The constraints given below guarantee that there will always be at least one array that matches the values Brus knows.
- For the constraints given below, the correct answer will always fit into an int.
Constraints
- n will be between 2 and 1,000,000, inclusive.
- d will be between 0 and 1000, inclusive.
- first will be between -1000 and 1000, inclusive.
- last will be between -1000 and 1000, inclusive.
- |first - last| will be at most (n-1)*d.
Examples
3
5
2
4
Returns: 7
Only the second element of the array is unknown. Its maximal valid value is 7.
10
100
999
100
Returns: 999
Due to the limitations, the first element is the largest element of the array.
1000000
0
474
474
Returns: 474
All elements of the array are equal.
97
53
-92
441
Returns: 2717
99
3
-743
-619
Returns: -535
96
6
-543
-275
Returns: -125
2
1000
444
-444
Returns: 444
2
999
0
0
Returns: 0
393417
561
-245
605
Returns: 110353232
727064
750
576
7
Returns: 272648826
497597
896
-92
-13
Returns: 222922916
529199
564
-743
-205
Returns: 149233093
852396
941
-543
-495
Returns: 401050882
596914
9
795
-849
Returns: 2686080
98837
669
-631
-430
Returns: 33060011
847367
413
-555
302
Returns: 174980937
140970
565
534
-906
Returns: 39823429
935547
27
828
-188
Returns: 12630186
908027
945
819
-612
Returns: 429042159
837390
198
-60
150
Returns: 82901550
847965
581
986
681
Returns: 246334223
418821
830
52
605
Returns: 173810352
379978
659
462
7
Returns: 125202554
402718
547
65
-13
Returns: 110142891
595696
627
257
-205
Returns: 186750326
125415
105
276
-495
Returns: 6584091
489029
545
631
-849
Returns: 133259826
697094
219
533
-430
Returns: 76331669
993689
718
394
302
Returns: 356734294
536302
409
370
-906
Returns: 109673262
1000000
1
995
681
Returns: 500837
999999
1
993
605
Returns: 500798
1000000
1
991
7
Returns: 500498
999999
0
990
990
Returns: 990
999999
0
997
997
Returns: 997
1000000
2
997
-495
Returns: 1000249
1000000
2
993
-849
Returns: 1000071
999999
1
999
-430
Returns: 500283
999999
0
992
992
Returns: 992
1000000
1
996
-906
Returns: 500044
19
11
1000
809
Returns: 1000
40
12
999
538
Returns: 999
29
12
999
671
Returns: 999
23
10
-959
-749
Returns: -749
74
14
-959
49
Returns: 49
23
10
-959
-750
Returns: -749
1000000
1000
-1000
1000
Returns: 499999000
100
3
2
9
Returns: 153
1000000
1
1
2
Returns: 500001
4
5
0
0
Returns: 5
10000
5
5
4
Returns: 25000
997901
313
997
-913
Returns: 156171376
3
100
1
0
Returns: 100
4
3
2
2
Returns: 5
7
8
1
11
Returns: 27
2
10
0
10
Returns: 10
5
2
2
5
Returns: 7
20
100
999
100
Returns: 1499
2
1
2
3
Returns: 3
30
10
30
20
Returns: 170
2
10
2
2
Returns: 2
100
1000
1
1000
Returns: 50000
1000000
1000
1
1
Returns: 499999001
3
2
1
5
Returns: 5
1000000
1000
-1000
-999
Returns: 499998001
2
3
2
4
Returns: 4
2
3
5
2
Returns: 5
2
239
-5
55
Returns: 55
2
8
5
10
Returns: 10
3
2
3
4
Returns: 5
3
2
100
100
Returns: 102
2
5
5
3
Returns: 5
1000000
1000
1000
1000
Returns: 500000000
4
1000
-1000
1000
Returns: 1000
1000000
2
-1
1
Returns: 999999
3
5
2
1
Returns: 6
1000000
1000
0
0
Returns: 499999000
3
100
100
100
Returns: 200
2
10
0
2
Returns: 2
3
4
4
4
Returns: 8
2
10
0
0
Returns: 0
2
1
5
4
Returns: 5
2
5
1
3
Returns: 3
2
298
-2
-1
Returns: -1
1000000
1
1
1
Returns: 500000
3
1
2
3
Returns: 3
3
1
1
1
Returns: 2
100000
10
10
9
Returns: 500000
2
2
12
14
Returns: 14
2
2
7
7
Returns: 7
1000000
1000
474
474
Returns: 499999474
2
1
3
2
Returns: 3
3
3
10
10
Returns: 13
1000000
1
0
0
Returns: 499999
3
1
-1
-1
Returns: 0
100000
5
345
23
Returns: 250180
2
100
1
1
Returns: 1
4
5
2
4
Returns: 9
4
10
-5
-6
Returns: 5
3
3
5
3
Returns: 6
5
1
0
0
Returns: 2
3
6
1
9
Returns: 9
4
100
98
100
Returns: 200
10
0
1
1
Returns: 1
2
3
1
2
Returns: 2
2
2
2
4
Returns: 4
2
1
1
2
Returns: 2
2
2
-3
-5
Returns: -3
2
7
-657
-654
Returns: -654
31
509
64
42
Returns: 7677
3
100
100
299
Returns: 299
4
5
0
15
Returns: 15
3
7
10
10
Returns: 17
3
3
4
7
Returns: 7
3
4
7
4
Returns: 8
2
5
-3
0
Returns: 0
2
10
7
16
Returns: 16
3
10
20
20
Returns: 30
2
1
4
5
Returns: 5
97
53
441
-92
Returns: 2717
3
5
10
5
Returns: 10
330465
961
35
-858
Returns: 158787094
1000000
987
-619
-718
Returns: 493498394
3
3
0
-2
Returns: 1
1000000
1000
123
765
Returns: 499999765