In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Approximation of a real function by another function is a task of finding such real function that has certain properties and can be used instead of with relatively small error. Most often is expected to be simpler than in some way and it should be possible to compute its values efficiently.
We define a staircase function as a real function such that its domain can be partitioned into intervals of the form (with and being some real numbers) satisfying the property that is constant on each of these intervals. Such interval for which is constant is called a stair of the function.
For simplicity let us assume that considered functions can change values only in points with integer -coordinate (so they are constant on any interval of the form where is an integer) and the domain we are interested in is .
We are interested in approximation of a staircase function which has at most stairs by functions having at most stairs. The error of approximation that we are willing to minimize is defined as:
for some value of the parameter .
Write a program which:
The first line of the input file contains three integers , and (, , ), separated with single spaces. denotes the number of stairs of function whereas denotes the maximum number of stairs of function . Each of the following lines contains one integer () - the value of at all points from the interval , where .
Remark: tests with different values of are not grouped together.
The first and only line of the output file should contain one non-negative real number - the error of the best approximation of by any -stair function . The difference between the actual answer and your program's answer must not be greater than .
For the input data:
6 3 1 0 3 3 2 9 0
the correct result is:
(for the correct answer would be ).
Task author: Krzysztof Duleba.