P15829 [JOI Open 2014] Secret

Anna invented a secret binary operation $\star$. For non-negative integers $x, y$ less than or equal to $1\,000\,000\,000$, a non-negative integer $x \star y$ less than or equal to $1\,000\,000\,000$ is determined. This operation $\star$ is associative. Namely, the equality $(x \star y) \star z = x \star (y \star z)$ holds for non-negative integers $x, y, z$ less than or equal to $1\,000\,000\,000$. This value is simply denoted by $x \star y \star z$. Anna planned to play a game with Bruno. She asked him to guess the operation $\star$. She showed $N$ integers $A_0, A_1, \dots, A_{N-1}$ to him. She gave to him a number of queries of the following form: “What is the value of $A_L \star A_{L+1} \star \cdots \star A_R$?” Bruno said it is difficult to play this game without hints. Anna decided to give hints to him. Each hint is given as follows: he will choose $x, y$ to ask the value of $x \star y$, and she will tell him the value of $x \star y$. He can ask for hints when the integers $A_0, A_1, \dots, A_{N-1}$ are given in the beginning of the game. He can also ask for hints when she gives a query to him. Of course, he would like to reduce the number of hints. Because he would like to behave as if he knows almost everything about the operation $\star$, he would especially like to reduce the number of hints after a query is given to him. ### Task Write a program which implements Bruno’s strategy to ask for hints and answer Anna’s queries correctly. ### Implementation Details You should write a program which implements the strategy to ask for hints and answer Anna’s queries. Your program should include the header file `secret.h` by `#include "secret.h"`. Your program should implement the following procedures. - `void Init(int N, int A[])` This procedure is called only once in the beginning. The parameter $N$ is the number $N$ of the integers shown by Anna. The parameter $A$ is an array of length $N$. The elements $A[0], A[1], \dots, A[N-1]$ are the integers $A_0, A_1, \dots, A_{N-1}$ shown by her. - `int Query(int L, int R)` This procedure is called when Anna gives a query to Bruno. This means she is asking the value of $A_L \star A_{L+1} \star \cdots \star A_R$ ($0 \leq L \leq R \leq N - 1$). This procedure should return the value of $A_L \star A_{L+1} \star \cdots \star A_R$. The following procedure can be called in your program. - `int Secret(int X, int Y)` This procedure is called when Bruno asks for a hint. This means he is asking about the value of $X \star Y$. The parameters $X$ and $Y$ should be integers $X$ and $Y$ satisfying $0 \leq X \leq 1\,000\,000\,000$ and $0 \leq Y \leq 1\,000\,000\,000$. If this procedure is called with parameters not satisfying this condition, your program is considered as **Wrong Answer [1]** and terminated. This procedure returns the value of $X \star Y$. ### Compilation and Test Run You can download an archive file from the contest webpage which contains a sample grader to test your program. The archive file also contains a sample source file of your program. A sample grader consists of one source file which is either `grader.c` or `grader.cpp`. For example, if your program is `secret.c` or `secret.cpp`, you run the following commands to compile your program. - **C** ```bash gcc -O2 -std=c11 -o grader grader.c secret.c -lm ``` - **C++** ```bash g++ -O2 -std=c++11 -o grader grader.cpp secret.cpp ``` When the compilation succeeds, the executable file `grader` is generated. Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output. ### Specification of the sample grader The sample grader assumes that Anna’s secret binary operation $\star$ is $x \star y = \min\left\{x + 2\left\lfloor \frac{y}{2} \right\rfloor, 1\,000\,000\,000\right\}$. Here, $\lfloor r \rfloor$ denotes the largest integer less than or equal to $r$. Note that this is different from the behavior of the actual grader.

The sample grader reads the following data from the standard input. - The first line contains an integer $N$, the number of the integers shown by Anna. - The second line contains space separated integers $A_0, A_1, \dots, A_{N-1}$, the integers shown by Anna. - The third line contains an integer $Q$, the number of queries given by Anna. - The $(j+1)$-st line ($0 \leq j \leq Q - 1$) of the following $Q$ lines contains space separated integers $L_j$ and $R_j$ ($0 \leq L_j \leq R_j \leq N - 1$). This means, in the $(j+1)$-st query, Anna asks the value of $A_{L_j} \star A_{L_j+1} \star \cdots \star A_{R_j}$.

When the program terminates successfully, the sample grader writes to the **standard output** the values returned by `Query` one per line. It also writes the following information to the **standard error**. - If your program is considered as **Wrong Answer [1]**, it writes “Wrong Answer [1]”. (The quotation mark is not written actually.) - If your program is not considered as **Wrong Answer [1]**, it writes the number of calls to `Secret` in the procedure `Init`, and the maximum number of calls to `Secret` in each call to the procedure `Query`.

### Sample interaction Here is a sample input for the sample grader and examples of interactions between the procedures. Note that the following return values are correct if the sample grader is used. | Input | |----------------| | 8 | | 1 4 7 2 5 8 3 6 | | 4 | | 0 3 | | 1 7 | | 5 5 | | 2 4 | | Call | Return | |-------------------------|--------| | Init(8, [1, 4, 7, 2, 5, 8, 3, 6]) | None | | Query(0, 3) | 13 | | Query(1, 7) | 32 | | Query(5, 5) | 8 | | Query(2, 4) | 13 | The procedure `Secret` can be called in the procedure `Init` or the procedure `Query`. For example, when `Secret(4, 7)` is called, the return value is 10 because $4 \star 7 = 10$ if the sample grader is used. The value of $1 \star 4 \star 7 \star 2$ is asked in the first query. Since $$ 1 \star 4 \star 7 \star 2 = (1 \star (4 \star 7)) \star 2 = (1 \star 10) \star 2 = 11 \star 2 = 13 $$ holds if the sample grader is used, the procedure `Query` should return 13. ### Constraints All input data satisfy the following conditions. - $1 \leq N \leq 1000$. - $0 \leq A_i \leq 1\,000\,000\,000$ ($0 \leq i \leq N - 1$). - The number of calls to `Query` is less than or equal to $10\,000$. ### Grading The score will be given to your program if your program terminates successfully for each test case, it is not considered as **Wrong Answer [1]**, and it returns the correct value for each call to `Query`. Your score is calculated as follows. (1) Your score is 100 if the following two conditions are satisfied for each test case: - In `Init`, the number of calls to `Secret` is less than or equal to 8000. - In each call to `Query`, the number of calls to `Secret` is less than or equal to 1. (2) Your score is 30 if your program does not satisfy (1), and the following two conditions are satisfied: - In `Init`, the number of calls to `Secret` is less than or equal to 8000. - In each call to `Query`, the number of calls to `Secret` is less than or equal to 20. (3) Your score is 6 if your program does not satisfy (1) or (2).