Two friends a and a are playing with an array of integers they both perform Operation on array but differ an choice of windows size to perform the said operation problem coding
Answers
Answer:
here is your answer mate
Explanation:
Array: 4 5 6 1 2 7 8 9
Window Size (W): 3
Output: 39
Explanation
· We will choose to add elements 4, 5, 6 since window size is 3.
· Since one addition operation is complete, we have to skip one element which is 1.
· We choose to skip element 2 because the next three values are also higher than 2.
· The max sum thus obtained is 39.
Now suppose the array was: 4 5 6 1 2 3 7 8 9
· We will choose to add elements 4, 5, 6 since window size is 3.
· Since one addition operation is complete, we have to skip one element which is 1.
· Now we choose to pick element 2 because we can skip element 3 and still pick up the next 3 values viz 7, 8, 9.
· The max sum thus obtained is 41.
· Note that we picked up only one element in second selection since constraint is only on maximum number to be chosen, not minimum.
Now suppose the array was: 4 5 6 7
· Since one can start from any index, we choose element 5, 6, 7.
· The max sum thus obtained is 18.
The above examples illustrate the game with a fixed window size of W. Since B prefers to play the same game with the size of W+D, the steps will remain the same but the max sum output may be different. Print different output depending on whether A wins, B wins or it’s a tie.
Constraints
0 <= N <= 10 ^ 5
5 <= W <= 10 ^ 5
-10^5 <= D <= 10^5
0 < (W + D) <= N
0 <= elements in array <= 10 ^ 9
Input
First line contains three space separated integers N and W and D respectively, which denote
N - size of array
W - window size
D - difference
Second line contains of N space separated integers denoting the elements of the array
Output
If B wins, print “Right ”
If A wins, print “Wrong ”
If It’s a tie, print “Both are Right”
Refer Examples section for better understanding.
Time Limit
1
Examples
Example 1
Input
8 5 -2
4 5 6 1 2 7 8 9
Output
Wrong 2
Explanation
Here we have given N = 8, W = 5, D = -2
A will maximize the sum of elements of the array using window size 5. Whereas B will maximize the sum of elements of the array using window size 3 (5-2).
Using logic as depicted above A will get the max sum as 41 and B will get the max sum as 39. The absolute difference is 41 - 39 = 2.
Hence, output will be: Wrong 2
Example 2
Input
9 2 2
4 5 6 1 2 3 7 8 9
Output
Right 10
Explanation
Here we have given N = 9, W = 2, D = 2
A will maximize the sum of elements of the array using window size 2. Whereas B will maximize the sum of elements of the array using window size 4 (2+2).
Using logic as depicted above A will get the max sum as 33 and B will get the max sum as 43. The absolute difference is 43 - 33 = 10.
Hence, output will be: Right 10