In short
You are given five integers $$$ n , a , b , c , d $$$ . You need to check if it is possible to form an array of $$$n$$$ elements such that each element's value is between $$$ a-b $$$ and $$$ a+b $$$ and the sum of the array is between $$$ c-d $$$ and $$$ c+d $$$
Initial Thoughts
My initial idea was to loop $$$ i $$$ from $$$ a-b $$$ to $$$ a+b $$$ and check if $$$ n * i $$$ lies in the range $$$ [ c-d , c+d ] $$$
But the problem with that is this assumes that all the array elements are same.
Counter Test
Let's have $$$ n = 4 , a = 2 , b = 1 , c = 7 , d = 1 $$$
This means that all the elements of the array we're trying to form is $$$ [ 1, 3 ] $$$ .
The sum we're trying to make is between $$$ [ 6 , 8 ] $$$
If we assume only same elements , the sum we can form are $$$ 3 , 6 , 9 $$$ ( All 3 elements are 1 or 2 or 3)
Intuition
Now in the previous case , this array is possible $$$ { 2 , 2 , 3 } $$$
How to generalize what sums are possible?
We know that the minimum sum possible is $$$ (a-b) * n $$$ (All elements are equal and are the smallest element)
The maximum sum possible is $$$ (a+b) * n $$$
Now are all the sums between $$$n * (a-b)$$$ and $$$n * (a+b)$$$ posssible ?
I took this example : $$$ n = 4 , a = 12 , b = 2 $$$
The goal is to prove that all sums from $$$ (a-b) * n $$$ to $$$ (a+b) *n $$$ are possible ie. between $$$ 40 $$$ and $$$ 56 $$$
Sum = $$$ 40 $$$ , Array = $$${ 10 , 10 , 10 , 10 } $$$
Sum = $$$ 41 $$$ , Array = $$${ 10 , 10 , 10 , 11} $$$ ...
Sum = $$$44 $$$ , Array = $$${ 10 , 10 , 10 , 14} $$$ or $$${11 , 11 , 11 , 11}$$$
Sum = $$$45$$$ , Array = $$${11 , 11 , 11 , 12} $$$
Sum = $$$46$$$ , Array = $$${11 , 11 , 11 , 13} $$$
Sum = $$$47$$$ , Array = $$${11 , 11 , 11, 14}$$$
Sum = $$$48$$$ , Array = $$${12 , 12 , 12 , 12}$$$
.....
Sum = $$$56$$$ , Array = $$${14 , 14 , 14 , 14}$$$
Doubts
My approach involved forming an array with $$$n-1$$$ equal elements and one same or different element , we can always from the sum $$$ n * (a-b) $$$ and $$$ n * (a+b) $$$
Do you try to prove such solutions especially if they're Div 2 , A
Is there an easy way to prove solutions
How to develop intuition ?
UPD Here is my attempt after reading Tzak's comment:
