lundi 5 janvier 2015

Check for a valid stastic?


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