Sereja conducted a voting about N of his opinions. Ai percent of people voted for opinion number i. This statistics is called valid if sum of all Ai is equal to 100.
Now let us define rounding up of a statistics A.
- If Ai is not an integer, it will be rounded up to next integer.
- Otherwise it will be left as it is.
Now let us consider a statistics B of size N in which each of Bi is an integer. Now he wants to know whether there exists some valid statistic A of size N (may contain real numbers) such that after rounding it up, it becomes same as B?
1 ≤ N ≤ 10000
Let’s define a small positive infinitesimal quantity e(epsilon).
For Bi, corresponding element in array A can be in range [Bi-1+e,Bi](both ranges included).
However, Bi = 0, the above range is invalid, so we’ll ignore all zero elements. Let’s say size of the remaining array B(after removing 0s) is N.
We now consider the lower and upper bounds on the sum of all numbers in A(note: any real number between these bounds can be generated). So, if 100 lies within these bounds, then answer is yes.
Now, what is the minimum possible sum? It’s S = [sum over all Bi] - N(number of non-negative elements in B) + e. So, we get condition for validity that S ≤ 100. If we ignore the e, we get S = [sum over all Bi] - N(number of non-negative elements in B) < 100.
Now, what is the maximum possible sum? It’s S = sum over all Bi. So, we get one more validity condition that S ≥ 100.
Note: Some people were confused about bounds on array A. A was not even in input.