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.