# Battleship

In this interactive problem you have to play a classic game of Battleship against one of the programs created by the scientific committee, which has been preset with more levels of difficulty.

The game is played on two 10x10 grids, one for each player. Before play begins, each player arranges their ships on their grid. Each ship occupies a number of consecutive squares on the grid, arranged either horizontally or vertically. The ships cannot overlap. Each player has 5 rectangular shaped ships with width 1: a destroyer (2 squares long), a cruiser (3 squares long), a submarine (3 squares long), a battleship (4 squares long) and an aircraft carrier (5 squares long).

After the ships have been positioned, the game proceeds in a series of rounds. In each round, each player takes a turn to announce a target square in the opponent's grid which is to be shoot at. The opponent then announces whether or not the square is occupied by a ship. When all of the squares of a ship have been hit, the ship is sunk, and the ship's owner announces this. If all of a player's ships have been sunk, the game is over and their opponent wins.

## Interaction instructions

At the beginning of the game you will have to print 5 different triplets of the format `x y type`, representing the coordinates of the upper left corner of the ship (x = line, y = column) and the type of orientation (0 = horizontal, 1 = vertical) of that ship (this information should be printed in increasing order of the ships' sizes). Then the game is played according to the following algorithm:

The first move of any round always belongs to you.

If itâ€™s your turn to make a move, you must print the coordinates of the cell you wish to target (of the format `x y`). If you hit a ship, but don't sink it, the computer's response will be `HIT`. If you miss completely, the response will be `MISSED`. If you sink a ship, the computer's response will be `SANK ship_type` (where `ship_type` is `destroyer`, `cruiser`, `submarine`, `battleship` or `aircraft carrier`).

If itâ€™s the computerâ€™s turn to make a move, it will print the coordinates of the cell it wants to target (of the format `x y`). You may read what the computer prints from stdin. After outputting each piece of information you must flush the output by either command (language dependent):

LanguageCommand
C++cout.flush()
Cfflush(FILE *output)
Java.flush() (i.e. method java.io.Console.flush())
PascalFlush(StdOut)
PythonWe do not reccomend this language for this particular task.

If the last shoot ordered by a player was a hit then that player is declared the winner, and the program will display the message `WINNER x` where `x` represents the winner (0 = you, 1 = computer). Nothing should be printed or written afterwards,therefore marking the end of the round, even though one of the players may not have made their move (this happens iff the first player wins, the second player not getting a chance to move in the last round).

The 2 matrices are 1-based indexed.

Your score will depend on how well you do agains our AIs.

The input and output is asymetric.

Questions?