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
EXPLANATION:
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.
LOWER BOUND:
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.
UPPER BOUND:
Now, what is the maximum possible sum? It’s S = sum over all Bi. So, we get one more validity condition that S ≥ 100.
There is no need to report it for each editorial: “According to editorialist’s answer it will be available a little later (as I understood for all problems).” Try let say in an hour or download someone’s ACed solution
Links are incorrect and redirecting to CHEFSTON…
I am deeply saddened by this problem… I did countless submissions and this was the first one which I think, follows the idea of the editorial apart from removing zeroes…
Was this (or any other of my submissions) the correct way to go apart from removal of zeroes?
Try this, n=5 : 0,34,34,35,0 correct anser is NO. Your code gives YES. http://ideone.com/hStNEd
Actually you didn’t check the number of terms which are non zero. Only they can be rounded, as 0 means the integed is already 0.
I was also getting frustrated, but then I realised that what if some elements are 0, they can NEVER be formed by rounding off as negative stats are invalid. It gave the right approach to AC: http://www.codechef.com/viewsolution/5818080
I think this one was difficult, because I do not know how to test it properly… Any idea someone? Something what can be used for let say 10-20 elements and always returns correct answer, but without the logic above (in case I had no such idea yet)?
I was thinking about something like for every number B[i], A[i] is in ( B[i] - 1, B[i] ] (interval). So try all possibilities let say B[i] and B[i] - 1 + 1/n for each element is not good, while for 51 51 it return. Problem also is, that generating 10-20 random numbers from [0-100] interval easily exceeds 100 + n sum limit…
What I can do, it to test YES answers - start with double 100 and divide it randomly = divide by some random factor to get two numbers (with sum 100) and repeat the process till I have n numbers, so I’ll have array A. But I feel like this is not very good test…
I think my solution was an easy one, no involving anything like comparisons with epsilon and even easy to test.
for(i=0;i<n;i++)
{
cin>>ele;
if(ele!=0)
sum+=(ele);
else
cnt++;
}
if(sum==100)
cout<<"YES\n";
else if(sum<100)
cout<<"NO\n";
else
{
// for all numbers as 0 and sum>100 -ve contirbution will give the minimum sum.
sum= sum- (n-cnt);
if(sum<100)
cout<<"YES\n";
else if(sum>100)
{
if((sum+cnt)<100) // taking care of elements whose value is zero
cout<<"YES\n";
else
cout<<"NO\n";
}
else
cout<<"NO\n";
}
Its just the matter of fact that I took care of negative contributions of the elements in the array B which can be zero.
I tried something like this, but this created problems as I used comparisons with float and double variables. But then the fact that “it is the second question of the contest with so many submissions”, I just thought the only thing that I am not given any decimal precision value. It can be any number of digits after decimal and thus I’ll be able to make 100 if possible as per the sum. So, I thought the below thing(my answer below).
