Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Matrix Resurrection

By Peregrine_Falcon · Limits 1s, 256 MB · Interactive

We have a two-dimensional matrix consisting of NN rows and MM columns. The rows are numbered from 11 to NN and the columns are numbered from 11 to MM. Two cells of the matrix will be called adjacent if they share a side vertically, horizontally, or diagonally.

Let’s say, we start with an empty matrix and fill it with integer numbers. To do that, first, we have to select a cell as the origin. We place integer 11 in the cell. Then we repeat the following steps until all the cells of the matrix are filled. At each step, first we find the largest number in the matrix. Then, for all the cells containing that number, we fill the adjacent empty cells with the immediately larger number.

For example, let’s assume: N=5N = 5 and M=5M = 5.

Let the origin of the numbers be at Row=3Row = 3 and Column=2Column = 2.
In step: 1, we will place integer 11 to the origin.
In step: 2, we will fill every adjacent cell of the origin with integer 22.
In step: 3, we will fill all the empty cells that is adjacent to the cells that contain integer 22 with integer 33.
In step: 4, we will fill all the empty cells that is adjacent to the cells that contain integer 33 with integer 44.

We have filled the matrix with numbers. But the process will go on in the case of a larger matrix. The steps are illustrated in the figure below:

This is an interactive problem. You will be given the size of the matrix. But the matrix will remain hidden. You can make at most 44 queries. In each query, you have to print the row and column numbers of a cell. And you will receive what number is hidden in that cell.

After the interaction, you will have to print the whole matrix.

Interaction

The first line of input will consist of two integers NN and MM (3N,M100)(3 \leq N, M \leq 100) indicating the number of rows and the number of columns respectively.

To make a query print “0 R C“. Here RR and CC (1RN,1CM)(1 \leq R \leq N, 1 \leq C \leq M) are the rows and column numbers respectively. You are allowed to make at most 44 queries of this type.

You will read an integer XX as a response to the query operation.

Here, XX is an integer situated in the RthR^{th} row and CthC^{th} column.

After you figure out the whole matrix, print integer 11. Followed by NN lines. Each line will consist of MM space-separated integer numbers which represent the hidden matrix.

Also, keep in mind that any other output from your program will end up getting "Wrong Answer" as a verdict. If you do not perform the interactions properly, you may receive a “CPU Limit Exceeded” verdict or any other verdict.

Here is what a possible interaction would look like for the example matrix of the problem statement.

> 5 5
< 0 3 3
> 2
< 0 3 2
> 1
< 1
< 3 3 3 3 4
< 2 2 2 3 4
< 2 1 2 3 4
< 2 2 2 3 4
< 3 3 3 3 4

> indicates what your program reads and < indicates what your program writes. These symbols are here to make it easy to understand. You do not have to print such symbols from your program.

Note

Since this is an interactive problem, don’t forget to flush your output after printing each line. You may use fflush(stdout) for printf/cout in C/C++, import sys and sys.stdout.flush() in Python to flush the output. If you use some other programming language, consult it's documentation.

To learn more about Interactive Problems: https://help.toph.co/toph/interactive-problems

Discussion

Statistics


46% Solution Ratio

IU_SpiralForgeEarliest, 1M ago

LUMBERJACK_MANFastest, 0.0s

NOxBODYLightest, 176 kB

NOxBODYShortest, 663B

Submit

Login to submit

Editorial

First, have a query for the upper left corner. Let the response be d1d1d1. Then query for the lower ...

Toph uses cookies. By continuing you agree to our Cookie Policy.