The new leadership of the national committee, represented by the coordinators of groups A and B, wishes to maintain a strict syllabus of the given problems for selecting the national team. For this purpose, they will need to give a geometry problem. Moreover -- the number of interactive problems given so far are below standard. To fix the crisis in the selection for , Sashka decided to give a problem that is both interactive and geometric. It has the following statement:
The jury has hidden a permutation of . You must find the permutation. For this purpose, you may ask the jury the following question: ``Is it possible to form a triangle with positive area with sides ?''
Note that it is known (by the triangle inequality) this is possible if and only if:
Write a program \textbf{\texttt{triangle}}, containing a function \texttt{solve}, which will be compiled together with the jury program and will communicate with it by asking questions of the type described above. At the end of its execution, it must determine the permutation.
Implementation details
You should implement the function:
std::vector<int>solve(intN)
: length of the permutation.
This function will be called times per test -- once per subtest, each with equal and it should return the hidden permutation for the subtest. In order to do this, your program can call the jury function :
boolquery(intA,intB,intC)
, , : indices of the sides .
The function returns , if a triangle with positive area with sides exists and , otherwise.
输入格式
Input format:
line : three integers , , and -- the number of subtests, the size of the permutations, and the execution mode. If , the local grader will generate uniformly random permutations and will expect a number on the second line -- , which will be the seed for its random generator. If , the input continues as follows:
lines to : permutations of .
输出格式
Output format:
line : an error message or the average number of queries for the subtests if all permutations are correctly identified.
样例
样例输入 1
样例输出 1
数据范围与提示
Sample Interaction
For this sample interaction , .
Contestant action
Jury action
solve(4)
query(0, 0, 0)
true
query(0, 1, 2)
false
query(0, 1, 3)
query(0, 2, 3)
true
query(1, 2, 3)
false
return {3, 1, 2, 4};
solve(4)
query(0, 1, 2)
false
query(0, 1, 3)
true
query(0, 2, 3)
false
query(1, 2, 3)
return {4, 2, 1, 3};
Constraints
Subtask
Subtask
Points
Description
The subtask consists of test with randomly and uniformly sampled from the set of all possible permutations, each of elements.
The points for a given subtask are obtained only if all the tests for it are successfully passed.
Scoring
Let be the average number of queries that your program makes for one call of on the single test, and let . Then your score for the problem will be:
