[Solution] Teleporters solution codeforces

Teleporters solution codeforces – There are 𝑛+1n+1 teleporters on a straight line, located in points 00𝑎1a1𝑎2a2𝑎3a3, …, 𝑎𝑛an. It’s possible to teleport from point 𝑥x to point 𝑦y if there are teleporters in both of those points, and it costs (𝑥𝑦)2(x−y)2 energy.

[Solution] Teleporters solution codeforces

You want to install some additional teleporters so that it is possible to get from the point 00 to the point 𝑎𝑛an (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?

Input

The first line contains one integer 𝑛n (1𝑛21051≤n≤2⋅105).

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎1<𝑎2<𝑎3<<𝑎𝑛1091≤a1<a2<a3<⋯<an≤109).

The third line contains one integer 𝑚m (𝑎𝑛𝑚1018an≤m≤1018).

Output

Print one integer — the minimum number of teleporters you have to install so that it is possible to get from 00 to 𝑎𝑛an spending at most 𝑚m energy. It can be shown that it’s always possible under the constraints from the input format.

[Solution] Teleporters solution codeforces

Examples
input

Copy
2
1 5
7
output

Copy
2
input

Copy
2
1 5
6
output

Copy
3
input

Copy
1
5
5
output

Copy
4
input

Copy
1
1000000000
1000000043

Teleporters solution codeforces

output

Copy
999999978

 

For Solution

Click here

Leave a Comment