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.
- 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 pascalRead: 2 5
Read: 2 1
Read: 2 2
Read: 2 4
Read: 3 3
Read: 4 4
Read: ver
Write: left
Read: hor
Write: downRead: 2 5
Read: 2 1
Read: 2 2
Read: 2 4
Read: 3 3
Read: 4 4
Read: hor
Write: up
Read: hor
Write: upYour 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 laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.