P17142 [NOI 2026] Pudding

The statement and sample attachments are from [QOJ](https://qoj.ac/contest/3938/problem/18985)。 When submitting to Luogu, there is no need to include the header `#include "pudding.h"`。Just copy ```cpp void init(int c, int t); int find_tastiness(int c, int m); int query_tastiness(std::vector a); ``` to the beginning of your program, and compile with C++17 or a higher version. **This is an interactive problem.**

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: ```cpp #include "pudding.h" ``` Contestants need to implement the following two functions in the submitted source file `pudding.cpp`: ```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. ```cpp 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: ```cpp int query_tastiness(std::vector 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.

### 【Test Program Mode】 You can compile an executable file in this problem directory using the following command: ```bash 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.

N/A

### 【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