> In the first example C=2; > When we buy the first pack, we will get one of the cards we need with > the probability 1. > f(2)=1*f(1)+1 > means that we expect to buy that many packs to get all the cards we > need. But we still don't know f(1). > For k=1 we have one card we need, and we need to find the other one. > When we buy this next pack, we will get the card we already have with > a probability 1/2 and the card we need with prob 1/2. > f(1)=1/2*f(1)+1/2*f(0)+1 > Then: f(1)=2; f(2)=3
I find f(x) in increasing order. f(x) represents the average cards needed to have all x cards. f(C) is the answer. For the C=2,N=1 example. f(2)=(f(1)+1)*1/2 + (f(2)+1)*1 //case 1: have one card, get another pack, and it's a new card //case 2: have two card, get another pack, and no new card. so we can only get f(1)<0, f(2) cannot be known. Obviously this method is wrong, but I don't know why. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
