|
|
I see many people had this WA. Can someone give me a hint about it? I think it will be useful for others. I had WA 4 because of wrong supposition: let probabilities are p0=1.0, p1, p2 p1 > p2 "p1" always should shoot into "p0" "p2" always should shoot into the air Thank you! There are really much more cases. Another way is to type (i-1) instead of (1-i) somewhere in your code without noticing and then spend 90 minutes going over the code and try to figure out how your logic could possibly be wrong. Since one paragraph says that "Each time a duelist may aim at any other alive duelist or purposely shoot in the air." But the next one says that "The first one (let's call him A) always hits his target and always aims at the best of the living rivals." Does it mean A always hits the guy who has greater shot accuracy? This is a problem with possible loops in decision. That means your decision will be based on others' decision, which might again be based on yourself. I think the best way to solve this sort of problems is to use ITERATION. I believe that some people could solve this directly. If you are like this, please post your idea or formula, I want to know it very much. During iteration, we must pay attention to the initialization value. If you have a bad init-value, you will not be able to move even one step in this problem. In my opinion, the init-value could be set as: when someone is starting a duel, then he could win this duel with prob 1. By the way, iteration will stop very quickly, as the calculation is unusual: there is function "MAX". So do not worry about the complexity of the problem. At last, some test-data here: 1.0 0.8 0.5 0.30000000 0.17777778 0.52222222 1.0 0.5 0.0 0.75000000 0.25000000 0.00000000 1.0 1.0 0.0 0.50000000 0.50000000 0.00000000 1 0.9 0.8 0.11000000 0.08265306 0.80734694 1 0.99999 0.99998 0.00001000 0.00001000 0.99998000 (Suprising or not?) 1 0.0001 0.0002 0.99975002 0.00014998 0.00010000 So, Good luck. Thanks for your hint. I got WA12, then I increase iteration to 5000 times, it ac now. My AC solution doesn't use iterations. It is based on some formulas. Rules of the forum says that I mustn't post my solution. But I can send my solution to you if you want to. Pay attention: players can shot in the air! YES "Each time a duelist may aim at any other alive duelist or purposely shoot in the air." Conditions are not defined fully. Let A killed and B,C presense. Optimal strategy for each: to shoot in air with pb=1 and pc=1. In such a situation every will have an incentive to shoot at other player. Pure prisoners' dilemma! The accuracy of A is equal to 1, and the accuracies of B and C are different With pB=pC=1 I meant objective functions for optimal strategy of B and C as probability to be alive. This maximal income achived when both shoot in air. This correspond to real life:if main aim to be alive peace is best solution. P.S. Having AC understood that such situation is absent in real tests for 1565. More exactly: the strategy have a next nature: when B and C are without A they shout to each other to kill one and geometric progressive appears. Edited by author 26.10.2007 18:54 Edited by author 26.10.2007 19:03 This is not correct. Take any book on game theory and read there the concept of Nash Equilibria. Then apply it to the solution of the problem and you'll find that if there are 2 players left, they will always shoot at each other. Why should anybody want to shoot in the air at any moment?????? That makes no sense: if you shoot in the air, your opponent will have more chance to kill you, since you skipped your turn! Let player B shoots first, and he is the weakest among all players (for simplicity, let we assume PC also = 1). If he shoots and kills any pleyer, then after shot of the player who alived he will definitely die. The best strategy for him is to shoot in the air and wait, while in the next turn player C kills player A, and then player B has a chance to win by killing C... Pay attention: players can shot in the air! Thanks! What means "The draw to determine the order of the shots is considered to be fair, that is, the order of the shots is unknown in advance" Does it means that player must choose to whom shoot before knowing order of the shots? It's bad translation and strange statement. The meaning is just that probabilities of all orderings are 1/6. My AC solution assumes that fighters know the order when they decide whom to shoot. Please, explain, why a man with smallest precision must not shoot before killing one of others, and give me some examples for testing my program |
|
|