6342번 - Treasure 점수다국어인터랙티브

After a recent earthquake, a new island has emerged in the Adriatic sea! The island is mostly barren except for an unusual device that was discovered. The name “oracle” quickly caught on for the device. Although the oracle came with no instruction manual, a crack team of archaeologists and computer experts was able to understand its behavior.

The oracle provides information about the locations of treasure on the island. The island is divided into a grid of cells consisting of N rows and N columns, with both rows and columns numbered 1 through N. Some of the cells in the grid contain treasure. The oracle answers questions of the form “Given a rectangle in the grid, how many cells in the rectangle contain treasure?”

Although the oracle answers questions for rectangles of all sizes, it was found that the more specific the information requested (the smaller the rectangle), the more energy is used by the oracle when answering. More precisely, if a rectangle contains S cells, then the oracle uses exactly 1 + N×N - S units of energy to answer.

Write a program that will, given the ability to interact with the oracle, find the locations of all cells on the island that contain treasure. We do not want to use too much energy in the process – the less energy is used, the better. It is not required that the amount of energy used is the smallest possible – see the “Grading” section for details on how your solution will be scored.

This is an interactive task. Your program asks the oracle questions using the standard output, and receives answers by reading from the standard input.

• At the beginning of your program, it should read an integer N (2 ≤ N ≤ 100), the size of the grid.
• To ask the oracle a question, your program should output a line containing four integers, R₁, C₁, R₂ and C₂, separated by spaces such that both 1 ≤ R₁ ≤ R₂ ≤ N and 1 ≤ C₁ ≤ C₂ ≤ N hold. If the conditions do not hold or the line is incorrectly formatted, your program will receive a score of zero on that test run.
• The oracle will respond with a line containing a single integer – the number of cells in the provided rectangle that contain treasure. More precisely, the number of cells (R, C) such that R₁ ≤ R ≤ R₂ and C₁ ≤ C ≤ C₂ and the cell at row R, column C contains treasure.
• When your program is done asking questions, it should output "END" on a single line. After that it should output N lines, one for each row in the grid, each containing a string of N characters "0" (zero) or "1" (one).The C-th character in the R-th line is "1" if there is treasure in the cell at row R, column C or "0" if not. Rows are numbered 1 to N top to bottom, columns left to right. The execution of your program will be automatically terminated once your program outputs a solution.
• In order to interact properly with the grader, your program needs to flush the standard output after each question and after writing the solution. The provided code samples show how to do this.

You may assume that, in each test run, the oracle will correctly answer questions and the locations of treasure will be chosen prior to the interaction. In other words, the grader is not adaptive and the answers will not depend on previous questions asked by your program.

Each test case is worth 10 points. If the output of your program is incorrect, you get zero points for that test case. Otherwise, the number of points awarded to your program depends on the total number of energy units K used by the oracle. More precisely:

• If K ≤ 7/16 N⁴ + N², your score is 10 points.
• Otherwise, if K ≤ 7/16 N⁴ + 2 N³, your score is 8 points.
• Otherwise, if K ≤ 3/4 N⁴, your score is 4 points.
• Otherwise, if K ≤ N⁴, your score is 1 point.
• Otherwise, your score is 0 points.

Additionally, in test data worth at least 40% of total points, N will be at most 20.

Your output will be considered correct even if your program guesses the correct solution, e.g. if it does not even ask a single question.