Alice and Bob have been unjustly sentenced to a maximum-security prison. Now they must plan their escape. To do this, they need to be able to communicate as efficiently as possible (in particular, Alice needs to send daily information to Bob). However, they cannot meet up and can only exchange information through notes written on napkins. Each day Alice wants to send a new piece of information to Bob – a number between and . At every lunch, Alice gets three napkins and writes a number between and on each napkin (there may be repetitions) and leaves them on her seat. Then, their enemy, Charly, destroys one of the napkins and mixes the other two up. Finally, Bob finds the two remaining napkins and reads the numbers on them. He must accurately decode the original number that Alice wanted to send him. There is limited space on the napkins, so is fixed. However, Alice and Bob's goal is to maximize the information throughput, so they are free to choose as large as they can. Help Alice and Bob by implementing a strategy for each of them, trying to maximize the value of .
Implementation details
Since this is a communication problem, your program will be run in two separate executions (one for Alice and one for Bob) that cannot share data or communicate in any way other than the one described here. You need to implement three functions:
intsetup(intM);
This will be called once at the start of Alice's execution of your program and once at the start of Bob's execution. It is given and must return the desired . Both calls to setup must return the same .
std::vector<int>encode(intA);
This implements Alice's strategy. It will be called with the number to encode () and must return three numbers () that encode . This function will be called a total of times - once per day (values of may repeat between days).
intdecode(intX,intY);
This implements Bob's strategy. It will be called with two of the three numbers returned by encode in some order. It must return the same value that encode received. This function will also be called times - corresponding to the calls to encode; they will be in the same order. All calls to encode will happen before all calls to decode.
样例
样例输入 1
样例输出 1
数据范围与提示
Example
Consider the following example with . Here we have an encoding scheme where Alice sends three equal numbers to encode or three distinct numbers to encode . Notice that Bob can decode the original number from any two of the three numbers Alice sent.
Execution
Function call
Return value
Alice
setup(10)
2
Bob
Alice
encode(0)
{5, 5, 5}
encode(1)
{8, 3, 7}
{0, 3, 1}
encode(0)
{7, 7, 7}
encode(1)
{6, 2, 0}
Bob
decode(5, 5)
0
decode(8, 7)
1
decode(3, 0)
decode(7, 7)
0
decode(2, 0)
1
Sample grader
For the sample grader, all calls to encode and decode will be in the same execution of your program. Additionally, setup will be called only once (as opposed to twice, once per execution, as in the grading system).
The input is just a single integer - . Then it will print out the your setup returned. It will then call functions encode and decode in this order times with randomly generated numbers from to and randomly generated choices of which two of the three numbers from encode to give to decode (and in what order). It will print out an error message if your solution failed.
Constraints
Scoring
For a particular subtask, the fraction of the points you get depends on the smallest returned by setup on any test in that subtask. It also depends on , which is the target value of that you need to get the full points for the subtask:
