let p=a/b,q=(1-c/d)*(1-a/b). The answer of this problem can be showed as:p*q^0+p*q^1+p*q^2+………… That is the sum of a geometric progression which is infinite but 0<q<1.We can get the limit by the formula:p/(1-q)
Obviously, It is about min-cut, which can be solved by max-flow. So, this problem can regarded as the minimum of losing money if we assume SmallR can get all the money and get a total money(sum of wi)at first. Define that, in the min-cut result, the dogs which are connected directly or indirectly to S are 0-gender.otherwise, those to T are 1-gender.We can easily find that the point of a initial-0-gender dog should get a vi weight edge to S.On the other way, initial-1-gender to T. Then, consider the rich men.As to each of rich men, he can appoint only one gender and some dogs.if any one dog he appoint is not the one appointed gender in the result, he can't give SmallR money.How to deal with the rich men in the graph is a difficulty.We can do this, make a new point for a rich man.Then, link the man's point to all points of his dogs by max enough weigh edges(which we can't cut in the min-cut algorithm), and link the man's point to S or T (which depend on that the man's appointed gender is 0 or 1) with a edge of wi weight. lastly run the min-cut(max-flow), we will get the minimum money we will lose. The answer is TotalMoney-LosedMoney. BTW, the issue of g is a piece of cake, we could add it to every special wi but not add it to the total money.
Can you explain please your solution to the problem about probability? I am not good at it, that's why i can't understand the idea... Why do you get this p and q?
P-вероятность того, что игра закончится после хода первого игрока.
Q-вероятность того, что игра продлится ещё один раунд.
И того складываем вероятность, что игра сразу закончится после 1-ого круга, после второго, третьего и т.д.
Настя, извини, что не на английском!
Sorry, but i can understand, why sometimes we have to count product of probabilities of 2 events, and sometimes we have to count their sums?
Excellent question.
SmallR, who shoots first can win in the following cases:
When there is an OR between 2 events(which lead to same result) happening, it means EITHER of them will lead to the same result, so the probability of the result is the SUM OF ALL THESE PROBABILITIES.
On the other hand, when there is AND between 2 events, it means that BOTH OF THEM SHOULD HAPPEN TO GET THE DESIRED OUTCOME. So if event A happens with probability = 1/2 and event B happens with probability = 1/2 and event C happens when both A and B happen, then probability of C happening is 1/2 * 1/2 = 1/4, which also makes sense logically. Because C will happen in only 1 out 4 cases, when BOTH A and B have happened. You can imagine the 4 cases:
So a good rule of thumb is AND means product of probabilities and OR means sum of probabilities.
So now we can get the answer to our problem:
answer = a/b + ( (1-a/b) * (1-c/d) * a/b ) + ( (1-a/b) * (1-c/d) * (1-a/b) * (1-c/d) * a/b )... and so on.
You can sum this up using formula for sum of infinite geometric series.
PS: I know this question was asked 3 years ago, but I hope this helps someone.
Helped me too, thanks!
Thanks
Thanks, helped me a lot!!!
312B - Archer can also be accepted by Brute Force, during contests this algorithm is more covenient for us. 3783547
I am not good at probabilities. Could you please explain what is the
nowvariable for. I mean, I understand te first two parts and why the for goes up to 1000000, I just can't understand is the update of the now. I also get that (1-z)*(1-r) is the combined probability that there is no winner at all..Thanks
It means the probability after some steps.
Hello,
This is my submission for problem D.Div1. My Machine output for the sample input is the same as the sample output. However, it displays different output here on CF machine.
Can anyone help me with this?
Try to code your own pow function. Function from cmath returns double, that is, for example, pow(3, 3) could return 26.99999 and became 26 when changed to int.
I edited my code and removed the 'pow' function but I got WA on test 2. Well, I don't know what is the wrong about my implementation. Do you have an idea?
Here is my new submission.
(a + b) ^ 3 is not equal to a ^ 3 + b ^ 3.