Equation Extrapolation
Following recent events, you got hooked on predicting the stock market and entered The Quant Cup, one of the most prestigious trading competitions in the world, where participants must predict the future of a simulated market. The challenge this year is more daunting than ever before, but after experimenting with the data provided by the organizers, you have stumbled upon a groundbreaking flaw. The data reveals that the asset prices in the simulation do not follow any random pattern. Instead, they seem to follow a hidden polynomial function \(P(x)\), where \(x\) represents a variable that influences the stock price. Figuring out this polynomial's coefficients would give you an unfair advantage in the competition, and you would definitely win. However, computing \(P(x)\) is a tedious and time consuming task, and the competition runs for just long enough so that you can make \(9\) such computations. Can you decode the hidden polynomial and take the lead in the competition?
More formally, there exists a hidden polynomial \(P(x) = a_0 + a_1x + a_2x^2 + \cdots + a_dx^d\) of degree \(d \ (0 \le d \le 10)\) with integer coefficients \(a_i \ (0 \le a_i \le 9\) for each \(i)\). Find the original polynomial and print its \(d + 1\) coefficients. To do this, you may query at most \(9\) integer values \(x \ (-10^6 \le x \le 10^6)\), and for each query, you will receive the value of \(P(x)\).
Interaction
This is an interactive problem. Your submission will be run against an interactor, which reads from the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:
Your program should make at most \(9\) queries to find the original polynomial. The polynomial's degree is not provided up front, it must be inferred from the queries. Each query is made by printing one line of the form "\(? \ x\)" with some integer \(x \ (-10^6 \le x \le 10^6)\). The interactor will respond with the integer value of \(P(x)\).
When you have determined all of the coefficients of the original polynomial, print one line of the form "\(! \ a_0 \ a_1\ ...\ a_d\)", where \(a_i\) is the coefficient of the \(x^i\) term in the original polynomial, after which the interaction will stop. Printing the answer does not count as a query.
The interactor is not adaptive: the coefficients are fixed up front, and do not depend on your queries.
Make sure you flush the buffer after each write.
A testing tool is provided to help you develop your solution.
Using more than \(9\) queries will result in a wrong answer.
Examples
Sample Interaction 1
| Read | Write |
|---|---|
? 4 |
|
313 |
|
? 7 |
|
1534 |
|
! 1 2 3 4 |
Sample Interaction 2
| Read | Write |
|---|---|
? 2 |
|
0 |
|
! 0 |
Sample Interaction 3
| Read | Write |
|---|---|
? 467 |
|
1094649 |
|
! 1 9 5 |
Comments