30909번 - Lateral Damage 다국어인터랙티브

문제

You are playing Battleships in a large ocean with large ships. More precisely, there is a large square grid of size at most 100ドル\times 100$ and inside it are up to 10ドル$ of the largest type of ship in Battleships -- the aircraft carrier -- which has a length of five tiles, placed either horizontally or vertically. The ships do not overlap, but they are allowed to be adjacent to each other. See Figure L.1 for an example.

Unfortunately, your opponent appears to bend the rules to their liking. It looks like they do not always determine the placement of their ships before you start shooting. You are not impressed by their attempt at cheating, and decide to try and win the game anyway.

Figure L.1: Illustration of Sample Interaction 1 after the first four shots were fired.

Your goal is to locate and sink all your opponent's aircraft carriers in at most 2500ドル$ shots, that is, you must hit each of the five tiles of all their ships.

입력

출력

제한

인터랙션

This is an interactive problem. Your submission will be run against an interactor, which reads from the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:

The interactor first sends one line with two integers $n$ and $k$ (5ドル \le n \le 100,ドル 1ドル \le k \le 10$), the size of the grid and the number of ships. It is guaranteed that it is possible to place $k$ aircraft carriers in the grid without overlap.

Then, your program needs to start firing shots. Each shot is fired by printing one line of the form "$x$ $y$" (1ドル \le x,y \le n$), indicating you shoot at position $(x, y)$. The interactor will respond with "hit" if the shot was a hit, "sunk" if the shot caused an aircraft carrier to sink, and "miss" otherwise. If you have shot the same location before, the response will be "miss".

Once you sink the last aircraft carrier, the interaction will stop and your program must exit.

The interactor is adaptive: the positions of the ships may be determined during the interaction, and may depend on where you decide to shoot.

Make sure you flush the buffer after each write.

A testing tool is provided to help you develop your solution.

Firing more than 2500ドル$ shots will result in a wrong answer.

힌트

첨부

• 1.in 2.in testing_tool.py