prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem D: </font> Find the Outlier</H1>3 4<p>5Professor Abacus has just built a new computing engine for making numerical tables. It was designed to calculate the values of a polynomial function in one variable at several points at a time. With the polynomial function <i>f</i>(<i>x</i>) = <i>x</i><sup>2</sup> + 2<i>x</i> + 1, for instance, a possible expected calculation result is 1 (= <i>f</i>(0)), 4 (= <i>f</i>(1)), 9 (= <i>f</i>(2)), 16 (= <i>f</i>(3)), and 25 (= <i>f</i>(4)).6</p>7 8<p>9It is a pity, however, the engine seemingly has faulty components and exactly one value among those calculated simultaneously is always wrong. With the same polynomial function as above, it can, for instance, output 1, 4, 12, 16, and 25 instead of 1, 4, 9, 16, and 25.10</p>11 12<p>13You are requested to help the professor identify the faulty components. As the first step, you should write a program that scans calculation results of the engine and finds the wrong values.14</p>15 16 17<H2>Input</H2>18 19<p>20The input is a sequence of datasets, each representing a calculation result in the following format.21</p>22 23<p>24<i>d</i><br/>25<i>v</i><sub>0</sub><br/>26<i>v</i><sub>1</sub><br/>27...<br/>28<i>v</i><sub><i>d</i>+2</sub><br/>29</p>30 31<p>32Here, <i>d</i> in the first line is a positive integer that represents the degree of the polynomial, namely, the highest exponent of the variable. For instance, the degree of 4<i>x</i><sup>5</sup> + 3<i>x</i> + 0.5 is five and that of 2.4<i>x</i> + 3.8 is one. <i>d</i> is at most five.33</p>34 35<p>36The following <i>d</i> + 3 lines contain the calculation result of <i>f</i>(0), <i>f</i>(1), ... , and <i>f</i>(<i>d</i> + 2) in this order, where <i>f</i> is the polynomial function. Each of the lines contains a decimal fraction between -100.0 and 100.0, exclusive.37</p>38 39<p>40You can assume that the wrong value, which is exactly one of <i>f</i>(0), <i>f</i>(1), ... , and <i>f</i>(<i>d</i>+2), has an error greater than 1.0. Since rounding errors are inevitable, the other values may also have errors but they are small and never exceed 10<sup>-6</sup>.41</p>42 43<p>44The end of the input is indicated by a line containing a zero.45</p>46 47 48<H2>Output</H2>49 50<p>51For each dataset, output <i>i</i> in a line when <i>v<sub>i</sub></i> is wrong.52</p>53 54<H2>Sample Input</H2>55<pre>562571.0584.05912.06016.06125.062163-30.5893962764645.763970839626539.38537980586674.37276631776746842.47153102466979.54202382027028.028239667571-30.362780752272-49.836348139373-25.5101480106747.5857576138175576-21.916169903877-48.46930427178-24.318857841779-2.3508594032480-9.7023920208681-47.270951062382-93.506624607283-82.507383649884085</pre>86 87<H2>Output for the Sample Input</H2>88<pre>89290191192693</pre>