Teleporters

题意翻译

## 题目描述 在一条直线上有 $n+1$ 个传送机，位于点 $0,a_1,a_2,a_3,...,a_n$. 如果在 $x$ 点和 $y$ 点都有传送机，那么可以从 $x$ 点传送到 $y$ 点，能量开销为 $(x-y)^2$. 你想安装一些额外的传送机，这样就可以从 $0$ 点传送到 $a_n$ 点（可能是通过其他传送机）且总共花费的能量不超过 $m$。**你安装的每个传送机必须位于整数点。** 现在你需要知道至少需要安装的传送机数量是多少。 ### 输入格式 第一行包含一个整数 $n (1 \le n \le 2 \cdot 10^5)$. 第二行包含 $n$ 个整数 $a_1,a_2,...,a_n (1 \le a_1 < a_2 < a_3 < ... < a_n \le 10^9$. 第三行包含一个整数 $m (a_n\le m\le 10^{18})$. ### 输出格式 输出一个整数，即你**至少**需要安装的传送机数量，使得从 $0$ 传送到 $a_n$ 的最多消耗能量值为 $m$。**数据保证永远有一个合法的答案。** Translated by @xzy090626

题目描述

There are $ n+1 $ teleporters on a straight line, located in points $ 0 $ , $ a_1 $ , $ a_2 $ , $ a_3 $ , ..., $ a_n $ . It's possible to teleport from point $ x $ to point $ y $ if there are teleporters in both of those points, and it costs $ (x-y)^2 $ energy. You want to install some additional teleporters so that it is possible to get from the point $ 0 $ to the point $ a_n $ (possibly through some other teleporters) spending no more than $ m $ energy in total. Each teleporter you install must be located in an integer point. What is the minimum number of teleporters you have to install?

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_1 < a_2 < a_3 < \dots < a_n \le 10^9 $ ). The third line contains one integer $ m $ ( $ a_n \le m \le 10^{18} $ ).

输出格式

Print one integer — the minimum number of teleporters you have to install so that it is possible to get from $ 0 $ to $ a_n $ spending at most $ m $ energy. It can be shown that it's always possible under the constraints from the input format.

输入输出样例

输入样例 #1

2
1 5
7

输出样例 #1

2

输入样例 #2

2
1 5
6

输出样例 #2

3

输入样例 #3

1
5
5

输出样例 #3

4

输入样例 #4

1
1000000000
1000000043

输出样例 #4

999999978