polski
Task Approximation (apr)
Approximation
Memory limit: 64 MB
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 
.
Task
Write a program which:
- reads a description of function
, the number of stairs of function 
and number 
from the standard input, - computes the best approximation of function
by a staircase function having at most 
stairs, - writes the error of approximation to the standard output.
Input
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.
Output
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 
.
Example
For the input data:
6 3 1 0 3 3 2 9 0
the correct result is:
4.00
(for 
the correct answer would be 
).
Task author: Krzysztof Duleba.