Zadanie : horner-2
Zadanie

Wielomian stopnia trzeciego W(x)=3x^3-5x^2+7x+9możemy zapisać w postaci Hornera następująco

W(x,0)=x \cdot(3x^2-5x+7)+9
.

Aby obliczyć jego wartość w punkcie x wystarczy do współczynnika ostatniego a_0=9 dodać pomnożoną liczbę x przez wartość w nawiasie, czyli wartość wielomianu o współczynnikach a_3=3, a_2=-5 a_1=7 - liczbę tę możemy oznaczyć przez W(x,1):

W(x, 1)=3x^2-5x+7=x\cdot (3x-5)+7
.

Jak widać obliczenie W(x,1) polega dokładnie na tym samym.

Wzór rekurencyjny pozwalający obliczyć wartość wielomianu stopnia n możemy zapisać następująco

W(x, i) = \begin{cases} a_n\text{, gdy }i=n\\ x \cdot W(x, i+1) + a_i\text{, gdy }i\lessdot n \end{cases}

a wartość wielomianu w punkcie x oblicza wywołanie W(x,0).

Napisz program obliczający wartość wielomianu rekurencyjną wersją schematu Hornera.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą k z zakresu 1..100000.
W każdym z kolejnych k wierszy zapisano liczbę całkowitą n z zakresu 0..10 będącą stopniem wielomianu, n+1 współczynników wielomianu z zakresu -1..1 oraz liczbę rzeczywistą x z zakresu -1..1. Współczynniki wielomianu zapisane są w kolejności od a0 do an.

Wyjście

W pierwszym wierszu wyjścia należy zapisać sumę wszystkich obliczonych wartości wielomianu z dokładnością do liczby całkowitej.
W wierszu drugim liczbę równą ilości takich wywołań funkcji rekurencyjnej, w których obliczony iloczyn x*W(x, i) był liczbą dodatnią.

Przykład

Dla danych podanych na wejściu:

2
2 1 1 -1 1.47
2 -1 1 -1 1.06

Poprawną odpowiedzią jest wyjście:

-1
0

Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5

Opcje zadania:

Biblioteki         : iostream iomanip cmath 
Limit czasu        : 0.25 s
Limit pamięci      : 32 MB
Słowa niedozwolone :