Coding Challenge — Greylock Tech Fair


RoboTreasureHunt

Problem

While spelunking in the Caribbean, you discover a secret labyrinth of caves, closed off from the outside. You analyze some surrounding sediment deposits, and find they contain traces of gold, but also poisonous sulfur.

Determined to excavate the caves and find all the gold, you plan your approach. From the sulfur deposits, you know the cave will have a poisonous atmosphere not safe for humans. So you plan to send in your trusty DrillBot to dig into each cave and get the gold. Each cave has a unique terrain which makes locating the exact gold locations difficult, but the DrillBot but can produce a two-dimensional map, where, each cell of the map contains the number of gold deposits on that cell's row and column.

For example, imagine the (hidden) locations of the gold deposits on the map are the following:

Specifically, there are four gold deposits, located at coordinates (1, 4), (2, 1), (4, 5), and (5, 0).

Then the DrillBot will produce the following map of the terrain:

Notice that, for example, cell (1, 0) has the number 2, which means there are a total of two gold deposits in row 0 and column 1. Given this numerical map, you must find the locations of these gold deposits so the DrillBot can drill exactly to the gold without over-drilling and destroying the structural integrity of the cave.

Input

You will be given a series of cases in a file, each containing a numerical mapping, and the number of gold deposits. The number of cases, C will be the first line of the file.

C cases follow. Within each case, the first line will contain three numbers, WH, and G, where W is the width of the grid, H is the height of the grid, and G is the number of gold deposits. The numbers will be separated by spaces. For example, in the above case, the first line would be the following:

7 7 4

After this, the grid will be printed out from top to bottom, as a series of space-separated numbers. For example, the grid in the above example would be represented as the following:

0 1 1 0 1 1 0
1 2 2 1 1 2 1
1 1 2 1 2 2 1
0 1 1 0 1 1 0
0 1 1 0 1 1 0
1 2 1 1 2 2 1
1 2 2 1 2 1 1

Output

For each test case, output G lines, containing the coordinates of the locations of the gold deposits, sorted first by y coordinate, then by x. For example, in the above case, the output would be the following:

5 0
2 1
1 4
4 5

Download and Submission

To help clarify the problem specification and desired output format, we have provided a small set of sample cases with their outputs below.

Sample Inputs   |   Sample Outputs

We have two groups of cases that you may solve. The first contains smaller inputs, and the second is a challenge set with larger inputs. You may submit solutions for either one (or both), along with your code. Please include a brief README describing which files are which, and any necessary instructions to run the code on the inputs.

Small Inputs   |   Large Inputs

To submit your solution, save all documents in a tarfile and email to careers@nuro.ai with the subject "Techfair Coding Challenge".

Good luck!