This is an interactive problem.
Flea Kingdom has an area of about 500 million square kilometers, inhabited by 400 million happy fleas. On a sunny morning, to enrich the lives of the fleas, the Flea King organized a high jump competition with $m$ fleas participating.
The competition is in the preparation stage. The $m$ fleas are standing in a line, numbered $1, \dots, m$. There are $n$ types of high jump techniques, numbered $1, \dots, n$. Each flea must choose one technique to perform their jump.
However, the Flea King's assistant, Volt, has seen through everything. Through long-term observation and research, he discovered that the $i$-th high jump technique can be represented by 3 parameters $a_i, b_i, c_i$. If the $k$-th flea uses the $i$-th technique, it will achieve a height of $a_i k^2 + b_i k + c_i$ meters. It is guaranteed that $a_i > 0$ and $b_i^2 - 4 a_i c_i \leq 0$.
The competition begins, but the fleas are not in a good state of mind and have adopted a conservative strategy: each flea chooses the technique that makes them jump the lowest.
Suddenly, the wind stopped, and smog immediately set in, with the air pollution index reaching five digits.
This stumped the Flea King. He needs to know the height of the flea that jumped the highest, but he cannot even find his own hands in the smog. The Flea King had to ask Volt for help. However, Volt originally intended to calculate the results of each flea by hand, only to find that he had forgotten the three parameters corresponding to each high jump technique!
The Flea King was helpless and had to kick Volt off the judge's stand to measure the contestants' results. The Flea King asks questions like: "Volt, how is the $k$-th flea doing?" Volt will carefully observe the high jump technique used by the $k$-th flea, obtain the three parameters $a_i, b_i, c_i$ of that technique, and run back to tell the Flea King.
However, the Flea King's reasoning ability is too weak, and he can only ask about each flea one by one in order, which would exhaust Volt. So, Volt found you. He wants you to teach the Flea King how to find the height of the highest-jumping flea by asking no more than $n$ questions.
Input
You need to write a function find_max to determine the height of the highest-jumping flea.
find_max(n, m)n: The number of high jump techniques $n$. It is guaranteed that $n \geq 1$.m: The total number of fleas $m$. It is guaranteed that $m \geq 1$.- This function should return the height of the highest-jumping flea.
You can call the function get to help you determine the height of the highest-jumping flea. We will score you based on the total number of times you call this function.
get(p, a, b, c)will query the three parameters of the high jump technique used by the $p$-th flea and assign them to $a, b, c$ respectively. If $p$ is outside the range $[1, m]$, this function will perform no operation.
Implementation Details
This problem only supports C++.
You must submit a single source file implementing the find_max function as described above, following the naming and interface conventions below.
You need to include the header file flea.h.
long long find_max(int n, int m);The interface for the get function is as follows:
void get(int p, long long *a, long long *b, long long *c);The function will assign the three parameters of the high jump technique to the variables pointed to by $a, b, c$.
If anything is unclear, see the examples and the provided grader, which includes sample programs.
Subtasks
There are 10 test cases, each worth 10 points. Let $t$ be the number of times your program calls the get function. If $t \leq n$, you get 10 points; otherwise, if $t \leq 5n$, you get 7 points; otherwise, if $t \leq 50n$, you get 4 points; otherwise, you get 0 points.
| Test Case Number | Special Constraints |
|---|---|
| 1 | $n = 10, m = 10$ |
| 2 | $n = 1$ |
| 3 | $n = 2$ |
| 4 | $n = 3$ |
| 5 | None |
| 6 | None |
| 7 | None |
| 8 | None |
| 9 | None |
| 10 | None |
For all test cases, $1 \leq n \leq 1000$, $1 \leq m \leq 10^6$. For each high jump technique, $1 \leq a_i \leq 1000$, $\left \lvert b_i \right \rvert \leq 10^9$, $\left \lvert c_i \right \rvert \leq 10^{15}$, and $b_i^2 - 4a_ic_i \leq 0$.
Examples
Input 1
3 1000000 326 -421505646 271727651175230 765 -593058832 140861873339701 291 -633539923 472231112710095
Output 1
146638735615726 3
Note 1
The $831493$-rd flea jumped the highest.
The second integer in the output, 3, is the total number of calls. You can consider this the output of a program that called the get function 3 times.
Input 2
See the provided files.