codeforces-scrape

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

908C.md (2036B)


      1 Source: https://codeforces.com/problemset/problem/908/C
      2 
      3 C. New Year and Curling
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Carol is currently curling.
     22 
     23 She has *n* disks each with radius *r* on the 2D plane.
     24 
     25 Initially she has all these disks above the line *y* = 10100.
     26 
     27 She then will slide the disks towards the line *y* = 0 one by one in order from 1 to *n*.
     28 
     29 When she slides the *i*-th disk, she will place its center at the point (*x**i*, 10100). She will then push it so the disk’s *y* coordinate continuously decreases, and *x* coordinate stays constant. The disk stops once it touches the line *y* = 0 or it touches any previous disk. Note that once a disk stops moving, it will not move again, even if hit by another disk.
     30 
     31 Compute the *y*-coordinates of centers of all the disks after all disks have been pushed.
     32 
     33 Input
     34 
     35 The first line will contain two integers *n* and *r* (1 ≤ *n*, *r* ≤ 1 000), the number of disks, and the radius of the disks, respectively.
     36 
     37 The next line will contain *n* integers *x*1, *x*2, ..., *x**n* (1 ≤ *x**i* ≤ 1 000) — the *x*-coordinates of the disks.
     38 
     39 Output
     40 
     41 Print a single line with *n* numbers. The *i*-th number denotes the *y*-coordinate of the center of the *i*-th disk. The output will be accepted if it has absolute or relative error at most 10- 6.
     42 
     43 Namely, let's assume that your answer for a particular value of a coordinate is *a* and the answer of the jury is *b*. The checker program will consider your answer correct if ![](https://espresso.codeforces.com/c97ba2000ebfad962bff7ffd8d043594f5ae1086.png) for all coordinates.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 6 2  
     51 5 5 6 8 3 12
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 2 6.0 9.87298334621 13.3370849613 12.5187346573 13.3370849613
     58 ```
     59 
     60 Note
     61 
     62 The final positions of the disks will look as follows:
     63 
     64  ![](https://espresso.codeforces.com/948fcb53d93866a46a676ebf7919a7a6476bca60.png) 
     65 
     66 In particular, note the position of the last disk.