ZOJ Problem Set - 3302
Recall the younger days when we had bought packets of stuff just to get the little collectibles inside, sometimes it's just so difficult to get the whole set!
Now, you are collecting candies and you started wondering about the numbers involved in your collection.
There are N kinds of candies of different colors, and in the vendor machine there are Ai of each kind.
Suppose you don't have any candies at the beginning. How many candies do you have to buy to gurantee that you have two candies of the same color? And the probablility of that happening? How many candies do yo have to buy to gurantee you have at least one of each color? And the probability of that happening?
There are multiple test cases. Each test case begins with the number N(1 <= N <= 100), the number of colors of candies in the vendor machine. Then there follows N integers, Ai(1 <= Ai <= 100), the number of candies of each color.
For each test case, output four numbers, the first is the number of candies you have to buy to gurantee that you have two candies of the same color, and the second is the probability of that happening, meaning you got two candies of the same color only after you bought the number of candies in the first output. The third number is the number of candies you have to buy to gurantee you have at least one of each color. And the fourth number is the probability of that happening, meaning you only got all colors after you bought so many candies as in the third output. If it's impossible for an event to happen, output -1 for the first or the third output and 0 for the second or the fourth output. Since working with float numbers and judging can and do lead to tragedies, in this problem you are to output the power of 2 in the answer for the second and the fourth output. For example, if the probability is 1/2 output -1, if it's 1/12 output -2, if it's 1/3 output 0, and if it's 2/9 output 1.
2 1 1 2 2 1
-1 0 2 0 3 1 3 0
In the second sample, to ensure that you get at least one of both kinds of candies, you must buy all three candies in the vendor machine, and the probability of that is 1/3, meaning that there is 1/3 probability that you got both kinds of candies only after you bought all three candies. Suppose the three candies are A,B, and C, and that A andf B are of the same color. Then of all the possible orders you can get the candies, ABC, ACB, BAC, BCA, CAB, CBA, ABC and BAC corresponds to the case where you got both kinds only after you bought all three candies and the others corresponds to the case that you only got two candies of the same color after you bought all three candies.
Author: SONG, Yu
Source: ZOJ Monthly, February 2010