codeforces-scrape

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

924B.md (2763B)


      1 Source: https://codeforces.com/problemset/problem/924/B
      2 
      3 B. Three-level Laser
      4 
      5 time limit per test
      6 
      7 1 second
      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 An atom of element X can exist in *n* distinct states with energies *E*1 < *E*2 < ... < *E**n*. Arkady wants to build a laser on this element, using a three-level scheme. Here is a simplified description of the scheme.
     22 
     23 Three distinct states *i*, *j* and *k* are selected, where *i* < *j* < *k*. After that the following process happens:
     24 
     25 1. initially the atom is in the state *i*,
     26 2. we spend *E**k* - *E**i* energy to put the atom in the state *k*,
     27 3. the atom emits a photon with useful energy *E**k* - *E**j* and changes its state to the state *j*,
     28 4. the atom spontaneously changes its state to the state *i*, losing energy *E**j* - *E**i*,
     29 5. the process repeats from step 1.
     30 
     31 Let's define the energy conversion efficiency as ![](https://espresso.codeforces.com/b1353c834ae20a0534a47916c2f0fbe98d7f4b7c.png), i. e. the ration between the useful energy of the photon and spent energy.
     32 
     33 Due to some limitations, Arkady can only choose such three states that *E**k* - *E**i* ≤ *U*.
     34 
     35 Help Arkady to find such the maximum possible energy conversion efficiency within the above constraints.
     36 
     37 Input
     38 
     39 The first line contains two integers *n* and *U* (3 ≤ *n* ≤ 105, 1 ≤ *U* ≤ 109) — the number of states and the maximum possible difference between *E**k* and *E**i*.
     40 
     41 The second line contains a sequence of integers *E*1, *E*2, ..., *E**n* (1 ≤ *E*1 < *E*2... < *E**n* ≤ 109). It is guaranteed that all *E**i* are given in increasing order.
     42 
     43 Output
     44 
     45 If it is not possible to choose three states that satisfy all constraints, print -1.
     46 
     47 Otherwise, print one real number η — the maximum possible energy conversion efficiency. Your answer is considered correct its absolute or relative error does not exceed 10- 9.
     48 
     49 Formally, let your answer be *a*, and the jury's answer be *b*. Your answer is considered correct if ![](https://espresso.codeforces.com/9507f804b12e83894b76ffa48fe1dcd911259459.png).
     50 
     51 Examples
     52 
     53 Input
     54 
     55 ```
     56 4 4  
     57 1 3 5 7
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 0.5
     64 ```
     65 
     66 Input
     67 
     68 ```
     69 10 8  
     70 10 13 15 16 17 19 20 22 24 25
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 0.875
     77 ```
     78 
     79 Input
     80 
     81 ```
     82 3 1  
     83 2 5 10
     84 ```
     85 
     86 Output
     87 
     88 ```
     89 -1
     90 ```
     91 
     92 Note
     93 
     94 In the first example choose states 1, 2 and 3, so that the energy conversion efficiency becomes equal to ![](https://espresso.codeforces.com/147ae7a830722917b0aa37d064df8eb74cfefb97.png).
     95 
     96 In the second example choose states 4, 5 and 9, so that the energy conversion efficiency becomes equal to ![](https://espresso.codeforces.com/f68f268de4eb2242167e6ec64e6b8aa60a5703ae.png).