cniks117's blog

312B archer
By cniks117, 12 years ago, In English

plz explain me how to approach this problem and the answer to this problem ..thnx in advance :)

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
12 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Probability of hitting the target by SmallR is a/b so missing the target is (1-a/b). Similarly for Zanoes, probability of missing the target is (1-c/d). Probability of hitting the target by SmallR in first go is a/b and Zanoes will not get his turn. If SmallR misses the target then Zanoes will get his turn but we are interested in first hit by SmallR so all try's by Zanoes must be misses. Probability of hitting the target in second go by SmallR is ( Probability of missing the target by SmallR at first go ) * ( Probability of missing the target by Zanoes at first go ) * ( Probability of hitting the target by SmallR at second go ) which is (1-a/b) * (1-c/d) * (a/b). Similarly probability of hitting the target at third go is (1-a/b) * (1-c/d) * (1-a/b) * (1-c/d) * (a/b) i.e missing in first two trials by Zanoes and SmallR and a hit in third try by SmallR. Sum of the values to infinty gives the probability that SmallR will hit first no matter what. This is a geometric progression with common ratio (1-a/b) * (1-c/d) which is less than 1 and hence sum of infinte values is a finite number.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you for your explanation. May I ask you one thing:

    In the problem description it says

    The answer will be considered correct if the absolute or relative error doesn't exceed 10^(-6)

    If we don't decide to solve the summation by hand in order to find the finite number, how can we know how many times we should loop in order to find the final result so that the error won't exceed 10^(-6)?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is infinitely long series where each value is multiplied by (1-a/b)*(1-c/d) which is less than 1. So each value is less than the previous value and at some point it will be almost 0 but we don't know when. Apparently we have a formula for such a series, you can see here

      [ sum = z * (1 / ( 1-r ) ); r=( ( 1-a/b ) * ( 1-c/d ) ) , z=a/b in this case ]

      So looping is not required, this formula is all we need . I hope i understood your question correctly.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      You should use while loop:
      while(delta>=EPS)
      {
      deltaX=(1-a/b)X(1-c/d);
      ans=ans+delta
      }

      → Reply