Hide

Problem J
Video Speedup

Anthony recently started watching YouTube videos with the title “X but every time Y happens it speeds up by Z”. He likes watching these videos because it saves time, but he wonders how much time he actually saves by watching these videos (instead of the originals).

You may assume that the new video X is exactly the same as the original video X, except certain segments of the new video play faster. Each time event Y happens, X speeds up by p%. Suppose event Y happens n times in X, and it happens at timestamps t1,t2,,tn (in seconds). That means the segment [0,t1) is playing at original speed, the segment [t1,t2) is playing at (100+p)% speed, the segment [t2,t3) is playing at (100+2p)% speed, and so on. Also, X is k seconds long.

Can you help Anthony compute the original length of the video?

Input

The first line of the input contains three integers n,p,k. It is guaranteed that 1n5000, 0p100, and nk20000.

The next line of the input contains n integers ti, denoting the timestamp of the event Y. It is guaranteed that the timestamps are given in chronological order, and that 1tik.

Output

A single number T denoting the length of the original video in seconds. Your answer is considered correct if its absolute or relative error is at most 106.

Sample Input 1 Sample Output 1
2 20 15
3 10
18.400
Sample Input 2 Sample Output 2
1 100 5
5
5.00
Hide

Please log in to submit a solution to this problem

Log in