C. Candy Boxes
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Ibor bought $$$n$$$ boxes of candies, and each box contains exactly $$$n$$$ candies.There is exactly one special box among them. All candies in this special box have a taste value of $$$v$$$, while all candies in the other $$$n - 1$$$ normal boxes have a taste value of $$$w$$$. It is guaranteed that the special candies taste better than the normal ones ($$$v \gt w$$$).

You are given the number of boxes, $$$n$$$. You need to figure out the normal taste $$$w$$$, the special taste $$$v$$$, and the 1-based index of the special candy box. To do this, you can ask Ibor to do the following procedure :

  • take any number of candies from any number of boxes. Ibor will return the total taste value of your selected candies.
You can ask Ibor at most $$$q$$$ times.

Implementation Details

You should implement the following procedure: 

std::vector< long long > find_candy(int n,int q)
  • $$$n$$$: the number of candy boxes.
  • The function must return a std::vector<long long> of size exactly $$$3$$$ containing the answers in this specific order: {w, v, idx}, where idx is the 1-based index of the special box.
  • $$$q$$$: maximum number of times you can ask Ibor for taste value
  • This procedure will be called exactly once by the grader.

The above procedure can make calls to the following procedure: 

long long taste_candy(std::vector< long long > a)
  • $$$a$$$: an array of size $$$n$$$. The element at $$$a[i]$$$ represents the number of candies you want to take from the $$$(i+1)^{th}$$$ box. $$$( 0\le i \lt n).$$$
  • The function returns the total sum of the tastes of all the candies in your array. More formally, $$$\sum (a[i] \times \text{taste of} (i+1)^{th} \text{box})$$$.
  • This procedure may be called no more than $$$q$$$ times.

Your code must not scan anything from the standard input (i.e. use scanf or cin) or print anything to the standard output (i.e. use printf or cout). However, you can print debugging information to stderr. For communication, use the functions described above. The grader is not adaptive. Meaning the value of $$$w$$$ $$$v$$$ $$$idx$$$ is fixed before a call to find_candy is made.

Constraints

  • $$$3 \le n \le 10,000$$$
  • $$$1 \le w \lt v \le 1000$$$
  • $$$1 \le q \le 10000 $$$
Input

Input format:

  • line 1:$$$n \ q \ w \ v \ idx$$$
Output

Output format:

  • line 1:'Returned:'$$$A$$$
  • line 2:'Expected:'$$$B$$$
  • line 3:'Queries:'$$$X$$$

Here, $$$A$$$ is the output of find_candy, $$$B$$$ is the original solution,$$$X$$$ is the number of all calls to taste_candy.

Note that the grader used for actual evaluation is different from the sample grader.

Scoring
SubtaskPointsAdd. constraints
$$$1$$$$$$40$$$$$$v=w+1, q=2$$$
$$$2$$$$$$60$$$No additional constraints

For the last subtask, your score is determined using a formula. Let's assume you asked Ibor total $$$X$$$ number of times. Your final score will be calculated using the following table:

XScore
$$$X \gt 10^4$$$$$$0$$$
$$$10 \lt X \le 10^4 $$$$$$40 \times \left( 1.15 - \left(\dfrac{\log_{10} X}{4}\right)^2 \right)$$$
$$$X \le 10$$$60
Example
Input
10 2 6 7 6
Output
Returned: {6, 7, 6}
Expected: {6, 7, 6}
Queries:  2
Note

Let's consider the following case.

$$$$$$n = 4,\quad q = 10000,\quad w = 6,\quad v = 7,\quad idx = 3$$$$$$

The following call will be made.

find_candy(4, 10000)

This procedure may call taste_candy as follows:

taste_candy({1, 1, 1, 1})

Suppose the query is made using the array $$$a$$$: $$$$$$a = [1, 1, 1, 1]$$$$$$

Since box 3 is special, taste_candy(a) returns:

$$$$$$ (1 \times 6) + (1 \times 6) + (1 \times 7) + (1 \times 6) = 25. $$$$$$

Using the returned values from the queries, you must determine $$$w$$$, $$$v$$$, and $$$idx$$$.