Alice conducted a voting about N of his opinions. A[i] percent of people voted for opinion number i.
This statistics is called valid if sum of all A[i] is equal to 100.
Now let us define rounding up of a statistics A.
If A[i] is not an integer, it will be rounded up to next integer. Otherwise it will be left as it is.
e.g. 4.1 became 5,
4.9 became 5 but 6 will still be 6.
Now let us consider a statistics B of size N in which each of B[i] is an integer. Now she wants to know where there exists some valid statistic A of size N (may contain real numbers) such that after rounding it up, it becomes same as B?
Example : Let N=3 and array B =[30,30,30] then answer is NO as there can not be any A which could be rounded up to get B. Hence answer is NO.
Also let N=2 and array be [50,51] then answer is YES as A = {49.5,50.5}. After rounding up we get {50,51} which is equal to B. Hence answer is YES.
What can be efficient algorithm to check this ?
Aucun commentaire:
Enregistrer un commentaire