English · Original
Chinese · Translation
Formal · Original
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.
Three distinct states _i_, _j_ and _k_ are selected, where _i_ < _j_ < _k_. After that the following process happens:
1. initially the atom is in the state _i_,
2. we spend _E__k_ - _E__i_ energy to put the atom in the state _k_,
3. the atom emits a photon with useful energy _E__k_ - _E__j_ and changes its state to the state _j_,
4. the atom spontaneously changes its state to the state _i_, losing energy _E__j_ - _E__i_,
5. the process repeats from step 1.
Let's define the energy conversion efficiency as , i. e. the ration between the useful energy of the photon and spent energy.
Due to some limitations, Arkady can only choose such three states that _E__k_ - _E__i_ ≤ _U_.
Help Arkady to find such the maximum possible energy conversion efficiency within the above constraints.
## Input
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_.
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.
## Output
If it is not possible to choose three states that satisfy all constraints, print _\-1_.
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.
Formally, let your answer be _a_, and the jury's answer be _b_. Your answer is considered correct if .
[samples]
## Note
In the first example choose states 1, 2 and 3, so that the energy conversion efficiency becomes equal to .
In the second example choose states 4, 5 and 9, so that the energy conversion efficiency becomes equal to .
元素 X 的一个原子可以处于 #cf_span[n] 种不同的状态，其能量为 #cf_span[E1 < E2 < ... < En]。Arkady 希望利用该元素构建一个激光器，采用三能级方案。以下是该方案的简化描述：
选择三个不同的状态 #cf_span[i], #cf_span[j] 和 #cf_span[k]，满足 #cf_span[i < j < k]。随后发生以下过程：
定义能量转换效率为 ，即光子有用能量与消耗能量之比。
由于某些限制，Arkady 只能选择满足 #cf_span[Ek - Ei ≤ U] 的三个状态。
请帮助 Arkady 在上述约束下找到可能的最大能量转换效率。
第一行包含两个整数 #cf_span[n] 和 #cf_span[U] (#cf_span[3 ≤ n ≤ 105], #cf_span[1 ≤ U ≤ 109]) —— 状态数量和 #cf_span[Ek] 与 #cf_span[Ei] 之间的最大允许差值。
第二行包含一个整数序列 #cf_span[E1, E2, ..., En] (#cf_span[1 ≤ E1 < E2... < En ≤ 109])。保证所有 #cf_span[Ei] 按递增顺序给出。
如果无法选择满足所有约束的三个状态，请输出 _-1_。
否则，输出一个实数 #cf_span[η] —— 可能的最大能量转换效率。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 9]，则被视为正确。
形式化地，设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，当 时你的答案被视为正确。
在第一个示例中，选择状态 #cf_span[1], #cf_span[2] 和 #cf_span[3]，使得能量转换效率变为 。
在第二个示例中，选择状态 #cf_span[4], #cf_span[5] 和 #cf_span[9]，使得能量转换效率变为 。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[U] (#cf_span[3 ≤ n ≤ 105], #cf_span[1 ≤ U ≤ 109]) —— 状态数量和 #cf_span[Ek] 与 #cf_span[Ei] 之间的最大允许差值。第二行包含一个整数序列 #cf_span[E1, E2, ..., En] (#cf_span[1 ≤ E1 < E2... < En ≤ 109])。保证所有 #cf_span[Ei] 按递增顺序给出。
## Output
如果无法选择满足所有约束的三个状态，请输出 _-1_。否则，输出一个实数 #cf_span[η] —— 可能的最大能量转换效率。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 9]，则被视为正确。形式化地，设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，当 时你的答案被视为正确。
[samples]
## Note
在第一个示例中，选择状态 #cf_span[1], #cf_span[2] 和 #cf_span[3]，使得能量转换效率变为 。在第二个示例中，选择状态 #cf_span[4], #cf_span[5] 和 #cf_span[9]，使得能量转换效率变为 。
**Definitions:**
- Let $ n \in \mathbb{Z}^+ $, $ U \in \mathbb{Z}^+ $, and $ E_1 < E_2 < \dots < E_n $ be strictly increasing energy levels.
- A valid triple $ (i, j, k) \in \mathbb{Z}^3 $ satisfies: $ 1 \leq i < j < k \leq n $ and $ E_k - E_i \leq U $.
- Energy conversion efficiency for triple $ (i, j, k) $ is defined as:
$$
\eta(i, j, k) = \frac{E_k - E_j}{E_k - E_i}
$$
**Constraints:**
- $ 3 \leq n \leq 10^5 $
- $ 1 \leq U \leq 10^9 $
- $ 1 \leq E_1 < E_2 < \dots < E_n \leq 10^9 $
- $ E_k - E_i \leq U $
**Objective:**
Maximize $ \eta(i, j, k) = \frac{E_k - E_j}{E_k - E_i} $ over all valid triples $ (i, j, k) $.
If no such triple exists, output $ -1 $.
---
**Formal Problem Statement:**
Given integers $ n $, $ U $, and a strictly increasing sequence $ E_1, E_2, \dots, E_n $, find:
$$
\max_{\substack{1 \leq i < j < k \leq n \\ E_k - E_i \leq U}} \left( \frac{E_k - E_j}{E_k - E_i} \right)
$$
If the feasible set is empty, return $ -1 $.
API Response (JSON)
{
"problem": {
"name": "C. Three-level Laser",
"description": {
"content": "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 descript",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF957C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 descript...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "元素 X 的一个原子可以处于 #cf_span[n] 种不同的状态，其能量为 #cf_span[E1 < E2 < ... < En]。Arkady 希望利用该元素构建一个激光器，采用三能级方案。以下是该方案的简化描述：\n\n选择三个不同的状态 #cf_span[i], #cf_span[j] 和 #cf_span[k]，满足 #cf_span[i < j < k]。随后发生以下过程：\n\n定义能量转...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n\n- Let $ n \\in \\mathbb{Z}^+ $, $ U \\in \\mathbb{Z}^+ $, and $ E_1 < E_2 < \\dots < E_n $ be strictly increasing energy levels.\n- A valid triple $ (i, j, k) \\in \\mathbb{Z}^3 $ satisfies:...",
"is_translate": false,
"language": "Formal"
}
]
}