Codah ClubTrain. Submit. Improve.
Sign in
English
#0001C5

z-cut

Little Z found his old Game Boy, and is playing his favorite game - Z-Cut. The game rules are:

- You are given a board of 2^N by 2^N fields, where N <= 10.
- M of the fields have coins on them (M <= 4^N).
- Then you play N rounds as following:
1) The computer chooses whether it wants to cut the board in half vertically or horizontally.
2) Then you choose which part of the board you want to keep

The goal of the game is to maximize the number of coins on the remaining board.

Help Mister Little Z by writing a program that will play the game optimally - maximize the number of coins on the remaining part of the board.




InputThis is an interactive task. First, from one line, read two integers N and M. From the next M lines read two integers x and y, representing the position of the coin on the board. 1 <= x, y <= 2^N. The fields are indexed starting from 1. After that, the following N times:

- From the next line read a string s. s will be either "hor" or "ver" - without quotes, meaning that the computer cut the remaining board horizontally (parallel with the x axis) or vertically (parallel with the y axis)
- To the next line write one string (don't forget the endl character). The string should be "up" or "down", if the board was cut horizontally, ir "left" or "right" if the board was cut vertically.

Also, make sure you ALWAYS flush the output before waiting for feedback. After writing the string, use:

cout.flush() in c++
fflush(stdout) in c
flush(output) in pascal


Example 1:
Read: 2 5
Read: 2 1
Read: 2 2
Read: 2 4
Read: 3 3
Read: 4 4
Read: ver
Write: left
Read: hor
Write: down



Example 2:
Read: 2 5
Read: 2 1
Read: 2 2
Read: 2 4
Read: 3 3
Read: 4 4
Read: hor
Write: up
Read: hor
Write: up


Your program will be tested against different strategies. In order for you to receive points for the test case, your program has to play optimally. In other words - you should play against the computer as if it had optimal strategy!

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.