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.