RGPC '17 P3 - Intercept

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

In today's math class, you learned how to find the equation of a polynomial function given its graph, but your friend Nemo did not, since he slept through the entire lesson. Needless to say, Nemo's act did not go unnoticed, and resulted in him being punished with extra homework questions to complete. Knowing that he won't have time to finish all of them, Nemo asks you, the best CS student in the school, to help him out.

Nemo is given Q extra questions, where each question gives him the x-intercepts (roots) of the polynomial function, as well as a pair of coordinates in the form (x, y), representing a point that lies on the function's graph. Can you determine what the coefficients of the equation are in standard form (a_N x^N + a_{N-1} x^{N-1} + \dots + a_0 x^0) for each question?

Note: all input and coefficients are guaranteed to fit in signed 64-bit integral variables (e.g. long long in C++).

Input Specification

The first line of input will contain the integer Q (1 \le Q \le 5). For each of the Q questions, there will be 3 lines:

  1. The integer N (2 \le N \le 10), representing the degree of the polynomial function.
  2. N space-separated integers x_i (-100 \le x_i \le 100), representing the x-coordinates of the roots of the function.
  3. Two space-separated integers x and y (-10 \le x \le 10, -10^{18} \le y \le 10^{18}) representing the coordinates of the known point.

Output Specification

Output a single line for each of the Q questions, containing N + 1 space-separated integers representing the coefficients of the function in standard form from the {a_N}^{th} term to the {a_0}^{th} term.

Sample Input

3 4
0 12
-2 3 4
0 48

Sample Output

1 -7 12
2 -10 -4 48


There are no comments at the moment.