Aproksymacja

Limit pamięci: 64 MB

Aproksymacja funkcji rzeczywistej inną funkcją rzeczywistą polega na znalezieniu takiej funkcji o zadanych własnościach, by dało się jej z powodzeniem używać zamiast . Zazwyczaj od funkcji oczekuje się, by była prostsza i dawała się szybciej wyliczać.

Funkcja schodkowa to funkcja, która jest stała na przedziałach lewostronnie domkniętych. Taki lewostronnie domknięty przedział, na którym funkcja przyjmuje tylko jedną wartość nazywamy schodkiem.

Dla uproszczenia przyjmiemy, że funkcje schodkowe mogą zmieniać wartości tylko w punktach o współrzędnych całkowitych (więc na każdym przedziale są stałe) i że są określone tylko na przedziale lewostronnie domkniętym .

Interesować nas będzie przybliżanie funkcji o schodkach za pomocą prostszych funkcji schodkowych o schodkach tak, by łączny błąd aproksymacji był mały. Błąd aproksymacji wyraża się wzorem

dla pewnego .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis funkcji i liczbę schodków funkcji oraz liczbę ;
• policzy najlepszą aproksymację funkcji za pomocą funkcji schodkowej o schodkach;
• wypisze błąd tej aproksymacji na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite dodatnie (liczba schodków funkcji , ), (liczba schodków funkcji , ) i (). W -tym spośród następnych wierszy znajduje się jedna liczba całkowita ( - wartość, którą funkcja przyjmuje na lewostronnie domkniętym przedziale .

Uwaga: testy o różnych wartościach nie będą grupowane razem.

Wyjście

Należy wypisać jedną liczbę rzeczywistš nieujemną, błąd najlepszej aproksymacji funkcji . Uznawane będą wyłącznie odpowiedzi różniące się co najwyżej o od oczekiwanego wyniku.

Przykład

Dla danych wejściowych:

6 3 1
0
3
3
2
9
0

poprawną odpowiedzią jest:

4.00

(dla odpowiedzią byłoby ).

Autor zadania: Krzysztof Dulęba.