Guess the Perimeter solution codeforces

Guess the Perimeter solution codeforces

Let us call a point of the plane admissible if its coordinates are positive integers less than or equal to 200200.

There is an invisible rectangle such that:

• its vertices are all admissible;
• its sides are parallel to the coordinate axes;
• its area is strictly positive.

Your task is to guess the perimeter of this rectangle.In order to guess it, you may ask at most 44 queries.

In each query, you choose a nonempty subset of the admissible points and you are told how many of the chosen points are inside or on the boundary of the invisible rectangle.

Interaction

To ask a query (of the kind described in the statement), you shall print two lines:

• In the first line print “kk” (without the quotes) where kk (k1k≥1) is the number of chosen points.
• In the second line print 2k2k integers x1,y1,x2,y2,,xk,ykx1,y1,x2,y2,…,xk,yk (1xi,yi2001≤xi,yi≤200 for i=1,2,,ki=1,2,…,k) where (x1,y1),(x2,y2),(x3,y3),,(xk,yk)(x1,y1),(x2,y2),(x3,y3),…,(xk,yk) are the kk distinct admissible chosen points (the order of the points is not important).

After this, you should read an integer — the number of chosen points that are inside or on the boundary of the invisible rectangle.When you have identified the perimeter pp of the invisible rectangle, you must print “pp” (without quotes) and terminate your program.

If you ask more than 44 queries or if one of the queries is malformed, the interactor terminates immediately and your program receives verdict Wrong Answer.

The interactor may be adaptive (i.e., the hidden rectangle may not be chosen before the beginning of the interaction).

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hacks

To hack a solution, use the following format.

The input has only one line, containing the 44 integers x0x0y0y0x1x1y1y1 (1x0<x12001≤x0<x1≤2001y0<y12001≤y0<y1≤200) — (x0,y0)(x0,y0) is the bottom-left vertex of the hidden rectangle and (x1,y1)(x1,y1) is the top-right vertex of the hidden rectangle.

Note that for hacks the interaction won’t be adaptive.

Examples

input

Copy
13 5 123 80

output

Copy

input

Copy
2 2 4 4

output

Copy

input

Copy
1 1 200 200

output

Copy

Note

The following is an example of interaction for the first sample intended to show the format of the queries.

Query (contestant program)? 413 5 13 80 123 5 123 80? 5100 4 100 81 12 40 124 40 50 50? 2200 200 1 1! 370Answer (interactor)410ExplanationWe choose the 4 vertices ofthe hidden rectangle.We choose 4 points just outside the hiddenrectangle and also the point (50,50).We choose the points (1,1)and (200,200).This is the correct perimeter.Query (contestant program)Answer (interactor)Explanation? 4We choose the 4 vertices of13 5 13 80 123 5 123 804the hidden rectangle.? 5We choose 4 points just outside the hidden100 4 100 81 12 40 124 40 50 501rectangle and also the point (50,50).? 2We choose the points (1,1)200 200 1 10and (200,200).! 370This is the correct perimeter.

For the second sample, a possible interaction is the following.

Query (contestant program)? 43 2 4 1 5 2 4 3? 71 4 2 4 1 5 2 5 5 5 5 6 6 5! 8Answer (interactor)21ExplanationWe choose the points (3,2)(4,1),(5,2) and (4,3).We choose the points (1,4)(2,4),(1,5)(2,5)(5,5)(5,6) and (6,5).This is the correct perimeter.Query (contestant program)Answer (interactor)Explanation? 4We choose the points (3,2), (4,1),3 2 4 1 5 2 4 32(5,2) and (4,3).? 7We choose the points (1,4), (2,4),1 4 2 4 1 5 2 5 5 5 5 6 6 51(1,5), (2,5), (5,5), (5,6) and (6,5).! 8This is the correct perimeter.

The situation is shown in the following picture: The green points are the ones belonging to the first query, while the orange points are the ones belonging to the second query. One can see that there are exactly two rectangles consistent with the interactor’s answers:

• the rectangle of vertices (2,2)(2,2) and (4,4)(4,4), shown in red;
• the rectangle of vertices (4,2)(4,2) and (5,5)(5,5), shown in blue.

Since both of these rectangles have perimeter 88, this is the final answer.