Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_12_20 - Funkcje tworzące

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 Δ4f(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: E3f(0) = f(3). Ogólnie Enf(0) = f(n). Jeżeli znajdziemy wzór na Enf(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) = Enf(0) = (1+Δ)nf(0) = f(0) + nΔf(0) + (n(n-1)/2)Δ2f(0) + (n(n-1)(n-2)/6)Δ3f(0) + ... W naszym szczególnym przykładzie Δ4f(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, Δ2f(0)=6, Δ3f(0)=6, znajdujemy f(n) = 0 + 2n + 3n(n-1) + n(n-1)(n-2), co upraszcza się do postaci f(n) = n3 + 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 E2 + 2E + 3. Przez (E2 + 2E + 3)f(n) rozumiemy oczywiście E2f(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+Δ)n 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 (D2 + 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 (ai ≤ 2 · 103).

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

Dodane przez:Mariusz Śliwiński
Data dodania:2021-01-11
Limit czasu wykonania programu:2s-5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY3 R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.