{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eWhile mostly known for the programs she wrote for Charles\n Babbage’s Analytic Engine, Augusta Ada King-Noel, Countess of\n Lovelace, described how the method of finite differences could\n be used to solve all types of problems involving number\n sequences and series. These techniques were implemented in\n Babbage’s Difference Engine.\u003c/p\u003e\n \u003cp\u003eThe algorithm: If we compute the difference between\n consecutive values in a numeric sequence, we will obtain a new\n sequence which is related to the derivative of the function\n implied by the original sequence. For sequences generated from\n first-order polynomials (linear functions) the successive\n differences will be a list of identical values, (i.e., a\n constant difference). For second-order polynomial functions the\n lists of differences will be a new sequence whose values change\n linearly. In turn, the list of differences of the values in\n this generated list (i.e., the finite differences of the list\n of differences) will be constant, and so on for higher-order\n polynomials. In general the \u003cspan class\u003d\"tex2jax_process\"\u003e$n^{\\text {th}}$\u003c/span\u003e row of differences\n will be constant for an \u003cspan class\u003d\"tex2jax_process\"\u003e$n^{\\text\n {th}}$\u003c/span\u003e degree polynomial.\u003c/p\u003e\n \u003cp\u003eFor example, the first-order polynomial \u003cspan class\u003d\"tex2jax_process\"\u003e$3x + 3$\u003c/span\u003e produces the sequence below\n at \u003cspan class\u003d\"tex2jax_process\"\u003e$x\u003d0,1,2,3,4$\u003c/span\u003e, and the\n first differences are shown on the following line.\u003c/p\u003e\n \u003cpre\u003e3 6 9 12 15 \n 3 3 3 3\n\u003c/pre\u003e\n \u003cp\u003eAs another example, the polynomial \u003cspan class\u003d\"tex2jax_process\"\u003e$x^2$\u003c/span\u003e, if evaluated at inputs\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x\u003d3, 5, 7, 9,$\u003c/span\u003e produces\n the sequence below.\u003c/p\u003e\n \u003cpre\u003e9 25 49 81\n 16 24 32\n 8 8\n\u003c/pre\u003e\n \u003cp\u003eFurthermore, if we consider a minimum-order polynomial that\n produces the original sequence, its value at the next regularly\n spaced input can be predicted by extending the difference\n table.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of a value \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, designating the number of\n polynomial evaluations given with \u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\leq n \\leq 10$\u003c/span\u003e, follwed by\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e values \u003cspan class\u003d\"tex2jax_process\"\u003e$v_1, v_2, \\ldots , v_{n}$\u003c/span\u003e which\n represent the value of a polynomial when evaluated at\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e regularly spaced input\n values. Each \u003cspan class\u003d\"tex2jax_process\"\u003e$v_ j$\u003c/span\u003e will\n satisfy \u003cspan class\u003d\"tex2jax_process\"\u003e$-2\\, 000\\, 000 \\leq v_ j\n \\leq 2\\, 000\\, 000$\u003c/span\u003e and at least two of those values\n will differ from each other.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput two integer values \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$v_{n+1}$\u003c/span\u003e, separated by a space. The\n value \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e must be the\n degree of a minimal-degree polynomial producing the original\n sequence, and \u003cspan class\u003d\"tex2jax_process\"\u003e$v_{n+1}$\u003c/span\u003e\n must be the value of the polynomial if evaluated at the next\n regularly spaced input value.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 3 6 9 12 15\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 18\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 9 25 49 81\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 121\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 39 6 -3 0 3 -6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3 -39\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}