영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
After solving the problem Light Show, you realize that the glaring white light can be used to illuminate certain squares in the grid. In this problem, you are given which squares should shine white and which should not, and your task is to place the lamps along the edge so that as many of the requirements as possible are met.
Input
The input consists of 10 test cases.
- The first line contains an integer T (0 ≤ T ≤ 10), the number of the test case (0 is the example case below).
- The second line contains two integers: n and m (1 ≤ n, m ≤ 1000), the number of rows and columns in the grid.
- The following n lines describe which squares should shine white and which should not. Each line will consist of a string with m ones and zeros. A one in row r and column c indicates that the square should shine white. A zero indicates that the square should not shine white.
Output
Print four lines with a string on each. The strings should represent a placement of lamps in the same format as the input in Light Show. Note that you should not print n and m.
Points
Your program will be tested on 10 test cases and scored based on how it performs relative to the judges' solution.
A solution's score for a specific test case is defined as max(0, x - nm/2), where x is the number of squares in the grid where the light from the lamps placed by the solution meets the given requirements for which squares should shine white and which should not. If your solution scored P_1 and the judges' solution scored P_2, you get 10 · (P_1 / P_2) points for the test case, rounded to two decimal places.
Your score for a submission is the sum of the scores for the test cases, and your total score is the score of the best submission. Thus, you cannot combine test cases between different submissions, but you must submit a single program that maximizes your score on all test cases simultaneously.
Your solution can receive a maximum of 100 points, even if it is better than the judges' solution.
The example test case will always give 0 points.
Explanation of Sample 1
In the example case, the solution meets all the requirements and its score is therefore 7.5, which is the maximum possible.
Test Cases
Here are descriptions of the 10 test cases that occur. Test cases of type 1 have been generated by taking the result of a random placement of lamps. There is therefore always a way to achieve the maximum nm/2 points on these test cases. Test cases of type 2 have been generated by randomly assigning each square to be a one or zero with 50% probability. These test cases often have no solution that meets all the requirements.
| Test Case | Limits | Type |
|---|---|---|
| 1 | n = 10, m = 10 | 1 |
| 2 | n = 40, m = 40 | 1 |
| 3 | n = 150, m = 150 | 1 |
| 4 | n = 400, m = 400 | 1 |
| 5 | n = 1000, m = 1000 | 1 |
| 6 | n = 100, m = 10 | 1 |
| 7 | n = 1000, m = 1 | 1 |
| 8 | n = 10, m = 10 | 2 |
| 9 | n = 100, m = 100 | 2 |
| 10 | n = 1000, m = 1000 | 2 |
예제
예제 1
0 3 5 00110 10101 10001
RRBBR RBB GRGBG GRB