codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2.md (3890B)


      1 Source: https://codeforces.com/blog/entry/107
      2 
      3 Lets start from the end.
      4 
      5 ## [Problem С. Commentator problem](https://codeforces.com/contest/2/problem/C)
      6 
      7 Let *R* be the distance from point А to a circle with center О and radius *r*. From this point the circle is observed at the angle ![](https://espresso.codeforces.com/038ac11e885a9e47bb7665eccfe526c14e675fb5.png).  
      8  So, the three stadiums are observed at the same angle if **R*1 / *r*1 = *R*2 / *r*2 = *R*3 / *r*3.*  
      9  Take two different points A, B. The set of points C that *AC* / *BC* = *const* is either a line (perpendicular bisector of AB) or a circle with center somewhere on the line AB. This circle is easy to find. It contains two points that lie on AB and satisfy *AC* / *BC* condition.  
     10    
     11 Let *X*1 be the set of points from which stadiums 1 and 2 are observed at the same angle. Let *X*2 be the set of points from which stadiums 2 and 3 are observed at the same angle. The answer belongs to both *X*1 and *X*2 . The centers of the three stadiums don't lie on one line, so the number of points in the intersection of  *X*1 and *X*2 will be finite.  
     12 Check them all. The answer is the point that lies closer to any of the stadiums. The stadiums don't intersect, so that point will not lie inside any of them.  
     13 How to get a big circle for *X*1 : put the centers of the stadiums in the points far away, for example in (0, 0) and (1000, 0). The ratio of the radii should be the closer possible to 1, for example ![](https://espresso.codeforces.com/33edbc1c2dee812dc0e341c9891dfd206d831630.png). The center and the radius of the new circle will have the order 106 . The answer should be known with 10- 5 precision. Roofly speaking, we need 11 digits, double precision will be enough.  
     14   
     15 
     16 ## [Problem B. The least round way](https://codeforces.com/contest/2/problem/B)
     17 
     18 Let us solve the problem in the case of positive matrix.  
     19 Let the number in the end be *N* = 2*k*· 5*m*·(other primes). The number of zeroes at the end of *N* is equal to *min*(*k*, *m*). At the aid of dynamic programming find minimal value of *k* (let it be *k*1) and minimal value of *m* (let it be *m*1), and paths that lead to these values. In case of *k*1 < *m*1 choose the path corresponding to *k*1, else  *m*1.   
     20  So *min*(*k*, *m*) is the upper bound for the answer. Let us prove that it is the lower bound too. If there exists a path leading to a number with number of zeroes less than *min*(*k*, *m*) then in the factorization of that number the power of two is *k* < *k*1 or the power of five is *m* < *m*1. We come to a contradiction.  
     21 So we need to calculate the power of 2 and 5 in the factorization of each value in the matrix and use dynamic programming on each of the two matrices.  
     22    
     23 In the case of matrix containing zeroes, calculate separately the best path not containing zeroes and any path containing zeroes:  
     24   
     25 Replace all 0by 10 and use the method described above. For paths containing zeroes the result will contain at least one zero at the end. If the method returned a number without zeroes at the end, the corresponding path is the answer, else any path containing zeroes is the answer.  
     26 The complexity of the algorithm depends on the complexity of the dynamics, it is *O*(*N*· *M*).  
     27   
     28 
     29 ## [Problem A. Winner](https://codeforces.com/contest/2/problem/A)
     30 
     31 Simple problem, just code it.  
     32  At the first pass calculate the sum of points for each player at game end. Let *M* be the maximum of these sums. At the second pass check every round. If current player *X* has not less than *M* points and his final score is equal to *M* then he is the winner.  
     33  The following test illustrates that player could receive more than *M* points, then lose some and, finally, win.  
     34  Input:   
     35  Masha 12  
     36  Masha -5  
     37  Sasha 10  
     38  Masha 3  
     39  Output:   
     40  Masha