루미 알고리즘

#1544플래티넘Light Show 2

PO 2022 온라인 예선코딩출제 Johan Sannemo, Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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 CaseLimitsType
1n = 10, m = 101
2n = 40, m = 401
3n = 150, m = 1501
4n = 400, m = 4001
5n = 1000, m = 10001
6n = 100, m = 101
7n = 1000, m = 11
8n = 10, m = 102
9n = 100, m = 1002
10n = 1000, m = 10002

예제

예제 1

입력
0
3 5
00110
10101
10001
출력
RRBBR
RBB
GRGBG
GRB

출처 표기

출처: Programmeringsolympiaden 2022년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.