Mirko is a big fan of crop circles, geometrical formations of flattened crops that are supposedly of alien origin. One summer night he decided to make his own formation on his grandmother's meadow. The great patriot that he is, Mirko decided to make a crop formation that would have the shape of the shield part of the Croatian coat of arms, which is a chessboard with red squares and white squares.
Grandma's meadow is a square divided into cells. The cell in the lower left corner of the meadow is represented by the coordinates and the cell in the upper right corner is represented by . Mirko decided to flatten only the grass belonging to red squares in the chessboard, leaving the rest of the grass intact. He picked an odd integer and flattened the grass so that each square of the chessboard comprises cells in the meadow, and the chessboard completely fits inside the meadow.
After Mirko went to sleep, his peculiar creation drew the attention of real aliens! They are floating high above the meadow in their spaceship and examining Mirko's crop formation with a simple device. This device can only determine whether the grass in a particular cell is flattened or not.
The aliens have found one cell with flattened grass and now they want to find the center cell of Mirko's masterpiece, so that they may marvel at its beauty. They do not know the size of each square in Mirko's formation.
Task
Write a program that, given the size of the meadow, the coordinates of one cell with flattened grass, and the ability to interact with the alien device, finds the coordinates of the center cell of Mirko's crop formation.
The device may be used at most times in one test run.
Interaction
This is an interactive task. Your program sends commands to the alien device using the standard output, and receives feedback from the device by reading from the standard input.
At the beginning of your program, you should read three integers and from the standard input, separated by single spaces. The number is the size of the meadow, while are the coordinates of one cell with flattened grass.
To examine the grass in the cell using the alien device, you should output a line of the form
examine X Y
to the standard output. If the coordinates are not inside the meadow (the conditions and are not satisfied), or if you use this facility more than 300 times, your program will receive a score of zero on that test run.The alien device will respond with a single line containing the word
true
if the grass in cell is flattened and the wordfalse
otherwise.When your program has found the center cell, it should output a line of the form
solution X_C Y_C
to the standard output, where are the coordinates of the center cell. You should terminate your program after outputting a solution.
In order to interact properly with the grader, your program needs to flush the standard output after every write operation.
If at any point you exceed the query limit or make an invalid query, the grader will output -1
and will exit.
You should terminate your program if the grader responds with -1
since it will not respond to any future queries.
Grading
In test cases worth a total of points, the size of each of Mirko's squares will be at most .
Each test run will have a unique correct answer that will not depend on the questions asked by your program.
In the following example, commands are given in the left column, row by row. Feedback from the alien device is given in the second column of the corresponding row.
Output (command) | Input (feedback) |
---|---|
19 7 4 | |
examine 11 2 | true |
examine 2 5 | false |
examine 9 14 | false |
examine 18 3 | true |
solution 12 9 |
Comments
this is actually pretty easy
this is actually pretty hard