FRAKTAL - konkurs programistyczny

Czasem trzeba dopasować funkcję do pewnego zbioru danych. Przypuśćmy, że mamy dane następujące informacje: dla pewnej funkcji f(0) = 0, f(1)=2 f(2)=10, f(3)=30, f(4)=68, f(5)=130, f(6)=222. Spodziewamy się, że do tych danych pasuje jakiś prosty wielomian. Czy tak rzeczywiście jest, a jeśli tak, to co to za wielomian? Dla podanego wyżej przykładu można sporządzić tablicę różnic:

n		0	1	2	3	4	5	6
f(n)		0	2	10	30	68	130	222
Δf(n)		2	8	20	38	62	92
Δ2f(n)		6	12	18	24	30
Δ3f(n)		6	6	6	6
Δ4f(n)		0 	0	0

Liczby każdego wiersza pokazują, ile wzrastają liczby poprzedniego wiersza. Pojawienie się samych zer w wierszu dla Δ⁴f(n) wskazuje, że istnieje jakiś prosty wzór na f(n). Jak go znaleźć? Najpierw określamy operację E, która przeprowadza f(n) w f(n+1). W szczególności Ef(0) = f(1), Ef(1) = f(2), Ef(2) = f(3). Zgodnie z tym f(0) można sprowadzić do f(3) stosując operację E trzy razy. Symbolicznie możemy to zapisać tak: E³f(0) = f(3). Ogólnie Eⁿf(0) = f(n). Jeżeli znajdziemy wzór na Eⁿf(0), to osiągniemy nasz cel.

Co można powiedzieć o operacji Δ? Weźmy pod uwagę jakąś szczególną liczbę z tablicy, np. 38, która jest równa Δf(3). Liczba ta jest różnicą 68-30, dwóch liczb poprzedniego wiersza, jest to różnica f(4) - f(3), ale f(4) = Ef(3), więc nasza liczba 38 jest równa Ef(3) - f(3), co możemy zapisać jako (E-1)f(3). Mamy więc Δf(3) = (E-1)f(3). To sugeruje, że operacja Δ jest to to samo, co operacja E-1. W liczbie którą wybraliśmy nie było nic specjalnego, dokładnie takie samo rozumowanie można by przeprowadzić dla każdej innej liczby tego wiersza. Przyjmujemy więc za prawdziwe, że Δ i E-1 reprezentują tę samą operację. Mamy więc Δ = E - 1, czyli E = 1+Δ.

Skorzystajmy teraz ze wzoru dwumianowego f(n) = Eⁿf(0) = (1+Δ)ⁿf(0) = f(0) + nΔf(0) + (n(n-1)/2)Δ²f(0) + (n(n-1)(n-2)/6)Δ³f(0) + ... W naszym szczególnym przykładzie Δ⁴f(0) wszystkie następne wyrazy są zerami, więc potrzebne nam są tylko wyrazy, które zostały napisane w ostatnim wyrażeniu. Podstawiając wartości z pierwszej kolumny naszej tablicy f(0)=0, Δf(0)=2, Δ²f(0)=6, Δ³f(0)=6, znajdujemy f(n) = 0 + 2n + 3n(n-1) + n(n-1)(n-2), co upraszcza się do postaci f(n) = n³ + n. Jest to szukany wzór, który spełnia podane na początku dane.

Metoda ta to przykład odwagi wobec formalizmu, przykład tego, że w matematyce można czasem nie być zbyt rygorystycznym, a mimo to dojść do poprawnego wyniku. Można tę metodę jednak uzasadnić w sposób logiczny. Zdefiniowaliśmy operator E, możemy pójść dalej i określić dowolny wielomian względem E, taki jak E² + 2E + 3. Przez (E² + 2E + 3)f(n) rozumiemy oczywiście E²f(n) + 2Ef + 3f(n), czyli f(n+2) + 2f(n+1) + 3f(n). Łatwo określić sumę dwóch takich wielomianów. Mnożenie definiuje się jako kolejne stosowanie operacji: (E+2)(E+3) polega na zastosowaniu najpierw operacji E+3, a do otrzymanego wyniku operacji E+2. Wielomiany względem E stanowią pierścień przemienny z elementem jednostkowym, stąd mamy prawo stosować do tego systemu twierdzenie dwumianowe. Ponieważ Δ = E-1, więc operacja Δ należy do naszego systemu i stosowanie wzoru dwumiennego do (1+Δ)ⁿ jest całkowicie uzasadnione.

Metoda znajdowania funkcji tworzących przedstawiona wyżej została w tym zadaniu podana raczej jako ciekawostka. Twoim zadaniem jest napisać program, który niezależnie od podanego ciągu liczbowego na wejściu, dla każdego testu wypisze liczbę, która znajduje się w przykładowym wyjściu. Dokładnie tę, na którą teraz patrzysz. Oczywiście, program twój może szukać kolejnego wyrazu ciągu podanego na wejściu, nie jest to jednak koniecznie, choć dopuszczalne. Ponieważ niemądrym byłoby teraz kończyć tekst na tym akapicie, więc poniżej rozpiszę się jeszcze trochę o wykorzystaniu podobnej metody opisanej wyżej dla rozwiązywania równań różniczkowych.

Z podobnego pomysłu korzysta się w jednej z metod rozwiązywania równań różniczkowych. Różniczkowanie oznaczmy przez D, Df(x) oznacza f'(x). Przez (D² + 2D +3) rozumiemy f''(x) + 2f'(x) + 3f(x). Mnożenie określamy jako kolejne stosowanie operacji: (D+2)(D+3) oznacza, że najpierw należy dokonać operacji D+3, a na otrzymanym wyniku dokonać operacji D+2. Okazuje się, że wielomiany względem D tworzą pierścień przemienny z elementem jednostkowym. Znów można z pełnym zaufaniem do wyników stosować wszystkie wzory algebry elementarnej, w których występuje tylko dodawanie, odejmowanie i mnożenie. Czasami o tej metodzie mówi się, że jest metodą odgadnięcia rozwiązania równania różniczkowego, bo zawsze trzeba sprawdzić jej poprawność względem wyniku jaki daje. Następnie okazuje się, że dziwnym zbiegiem okoliczności wyniki zawsze są poprawne.

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się dziewięć początkowych wyrazów pewnego rosnącego ciągu liczbowego (a_i ≤ 2 · 10³).

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę, o której mowa w treści zadania.

Przykład

Wejście

14 29 68 143 266 449 704 1043 1478

Wyjście

2021