Background

The statement and sample attachments are from QOJ。

When submitting to Luogu, there is no need to include the header #include "pudding.h"。Just copy

void init(int c, int t);
int find_tastiness(int c, int m);
int query_tastiness(std::vector<int> a);

to the beginning of your program, and compile with C++17 or a higher version.

This is an interactive problem.

Problem Description

Both Little $L$ and Little $S$ really like sweet and soft pudding. After tasting many kinds of pudding, they quantify the tastiness of every pudding as a positive integer not exceeding $4500$。

Little $L$ is learning to make pudding. Due to limited skill, she can only make pudding whose tastiness does not exceed a constant $m$。In one attempt, Little $L$ successfully made a piece of pudding with tastiness $w$。Little $S$ wants to taste the pudding made by Little $L$, but she must determine the tastiness of the pudding in the way required by Little $L$。

Specifically, Little $S$ can buy several puddings from the store and give them to Little $L$。Little $L$ will mix in the pudding she made, sort all these puddings in nondecreasing order of tastiness, then compute the sum of the greatest common divisors of all adjacent puddings’ tastiness values, and tell the result to Little $S$。Finally, she will eat all the puddings that Little $S$ bought.

Formally, suppose Little $S$ buys $k$ puddings with tastiness values $a_0,a_1,\ldots,a_{k-1}$。Let the sorted result of $[a_0,a_1,\ldots,a_{k-1},w]$ be $[b_0,b_1,\ldots,b_{k-1},b_k]$。Then Little $L$ will tell Little $S$ the value of $\sum_{i=1}^{k}\gcd(b_{i-1},b_i)$。

Since both the time cost of going to the store and the economic cost of buying puddings are high, Little $S$ hopes to minimize both the number of purchases and the total number of puddings bought. You need to help Little $S$ design a buying strategy to determine the tastiness of the pudding made by Little $L$。

【Implementation Details】

Contestants do not need to, and should not, implement the main function.

Contestants must ensure that the submitted program includes the header pudding.h, i.e., add the following code at the beginning of the program:

#include "pudding.h"

Contestants need to implement the following two functions in the submitted source file pudding.cpp:

void init(int c, int t);

• $c,t$ denote the test point ID and the number of testdata groups, respectively. $c=0$ means this test point is the sample.
• For each test point, this function will be called by the interaction library exactly once when the program starts.

int find_tastiness(int c, int m);

• $c,m$ denote the test point ID and the upper bound of the tastiness of the pudding made by Little $L$, respectively.
• This function should return a positive integer $w$, which is the tastiness of the pudding made by Little $L$。
• For each test point, this function will be called by the interaction library exactly $t$ times.

Contestants can make one query by calling the following function:

int query_tastiness(std::vector<int> a);

• $a$ is the sequence of tastiness values of the puddings bought by Little $S$。You must ensure that $a$ is non-empty, and every element is a positive integer not exceeding $4500$。
• This function returns the value told by Little $L$ to Little $S$, as described in 【Description】.
• You must ensure that, in each call of find_tastiness, the number of calls to this function does not exceed $15$, and the total sum of the lengths of $a$ over all calls does not exceed $3000$。

In any case, the time required by the interaction library will not exceed $1.5$ seconds, and the memory usage will not exceed $64\ \mathrm{MiB}$。

The file template_pudding.cpp in this problem directory is the provided sample code. You may refer to it and implement your own code.

Input Format

【Test Program Mode】

You can compile an executable file in this problem directory using the following command:

g++ grader.cpp pudding.cpp -o pudding -O2 -std=c++14 -static

For the compiled executable file pudding:

• The executable reads input from standard input in the following format:
  • The first line contains three non-negative integers $c,t,m$。
  • The second line contains $t$ positive integers, which are the values of $w$ for each group of testdata.
• The executable outputs to standard output in the following format:
  • If the return values of find_tastiness are all correct for the $t$ calls, then:
    • The first line is Correct!。
    • The second line is Max queries used: Q, where $Q$ is the maximum number of calls to query_tastiness among all testdata.
    • The third line is Max total puddings queried: S, where $S$ is the maximum, among all testdata, of the sum of the lengths of $a$ passed to query_tastiness.
  • If at least one call to find_tastiness returns an incorrect value, then only one line Wrong answer. is printed.
• If the parameter passed to query_tastiness does not meet the requirements, or the number of calls exceeds the limit, the executable will output an error message to standard error and return $-1$。
• You can enable the -v or --verbose option when running the executable file. In this case, the executable will additionally output:
  • The return value of each call to find_tastiness, its correctness, the number of calls to query_tastiness, and the sum of the lengths of $a$ passed to it.
  • The parameters passed to query_tastiness for each call, the computation process, and the return value.
  • The final score ratio obtained by the program. See the section 【Scoring】 for details.

0 2 197
26 121

Correct!
Max queries used: 2
Max total puddings queried: 5

Hint

【Sample $1$ Explanation】

For the first group of testdata, the tastiness of the pudding made by Little $L$ is $26$。Below is one possible interaction process:

• Call query_tastiness ($[2026,7,20]$). Then $b=[7,20,26,2026]$, so the function returns $\gcd(7,20)+\gcd(20,26)+\gcd(26,2026)=1+2+2=5$。
• Call query_tastiness ($[13,52]$). Then $b=[13,26,52]$, so the function returns $\gcd(13,26)+\gcd(26,52)=13+26=39$。
• Return $26$, which is correct.
• The number of calls to query_tastiness is $2$, and the sum of the lengths of $a$ passed to query_tastiness is $3+2=5$。

【Sample $2$】

See pudding/pudding2.in and pudding/pudding2.ans in the contestant directory.

This sample satisfies the constraints of test point $1$。

【Sample $3$】

See pudding/pudding3.in and pudding/pudding3.ans in the contestant directory.

This sample satisfies the constraints of test point $2$。

【Sample $4$】

See pudding/pudding4.in and pudding/pudding4.ans in the contestant directory.

This sample satisfies the constraints of test point $3$。

【Constraints】

For all testdata:

• $1\le t\le3000$；
• $1\le m\le3000$，$1\le w\le m$。

::cute-table{tuack} | Test point ID | Score | $t=$ | $m=$ | Special property | |:-:|:-:|:-:|:-:|:-:| | $1$ | $10$ | $35$ | $35$ | None | | $2$ | $20$ | $430$ | $3000$ | $A$ | | $3$ | $70$ | $3000$ | $3000$ | None |

Special property $A$: $w$ is a prime number.

【Scoring】

Note:

• Contestants should not obtain internal information from the interaction library by illegal means, such as trying to directly read the value of $w$, or directly interacting with standard input and output streams. Such behavior will be considered cheating.
• The interaction library is non-adaptive, i.e., in each call to find_tastiness, the value of $w$ is already fixed and will not change during the interaction process.
• The final judging interaction library is implemented differently from the sample interaction library. If the return value of find_tastiness is incorrect, or the parameter passed to query_tastiness does not meet the requirements, then the corresponding test point gets $0$ points. Under the above conditions:
• For each test point, let $Q$ be the maximum number of calls to query_tastiness among all testdata, let $S$ be the maximum, among all testdata, of the sum of the lengths of $a$ passed to query_tastiness, and let $\mathrm{score}$ be the score of this test point. The program obtains $\left\lfloor f(Q)\cdot g(S)\cdot\mathrm{score}\right\rfloor$ points, where $f$ and $g$ are computed as follows.

::cute-table{tuack} | $Q$ | $f(Q)$ | |:-:|:-:| | $Q\le4$ | $1$ | | $5\le Q\le15$ | $0.7^{Q-4}$ |

::cute-table{tuack} | $S$ | $g(S)$ | |:-:|:-:| | $S\le35$ | $1$ | | $36\le S\le75$ | $1-\dfrac{S-35}{100}$ | | $76\le S\le235$ | $0.2+\sqrt{\dfrac{235-S}{1000}}$ | | $236\le S\le3000$ | $0.2\times2^{-\frac{S-235}{1500}}$ |

Translated by ChatGPT 5