27349번: Coins

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	1024 MB	10	1	1	100.000%

문제

There are coins placed on squares of a $N \times N$ grid board where $N$ is even. There is one coin in each square. Exactly half of the coins are silver ones, the other half are copper.

The coins are placed properly if all the copper coins are in the upper left part of the board and silver coins are placed on the lower right part of the board. To be precise, if the edge of a square is a separator between different types of coins, the copper coin is either to the left or above the silver coin.

Proper placement	Improper placement

Figure 1: The coins are placed properly if there are no placements as shown on the right. Black circles represent copper coins, white circles – silver ones.

You are given a set of coins placed improperly on the board. Rearrange them to get a proper placement by switching as few pairs of coins as possible.

입력

The first line of the input contains four integers – $T$, $N$, $K_1$, $K_2$:

$T$ – the number of the test;
$N$ – board size;
$K_1$, $K_2$ – values that define grading (see section Grading).

Each of the remaining $N$ lines contain $N$ integers each. They describe initial coin placement on the board. Available integers are 0 (copper coin) or 1 (silver coin).

출력

Output the board with proper placement of coins in a form of $N \times N$ board in the same format as input. Exactly one half of integers should be 0 (copper coin), the other half should be 1.

예제 입력 1

예제 출력 1

The coins in the solution are placed properly. Three pairs of coins were swapped, therefore based on grading description (see section Grading), it would score $10 · (6 - 3)/(6 - 1) = 6.0$ points. All $10$ would be awarded for the following solution:

Note that this test is sample test. It does not belong to the set of $10$ tests that will be graded.

채점

There are ten tests numbered from $1$ to $10$ to grade the solutions. Solutions to each test are evaluated separately and for each test is worth $10$ points.

If your program outputs incorrect solution or exceeds time or memory limits, or does not produce a solution due to run-time error or another reason, no points are awarded for the test.

If your program provides correct solution, the awarded points depend upon the number of pairs of coins that have to be swapped in the input to get the solution provided by your program. Let us denote this number as $K$. For each test you will get full $10$ points if $K ≤ K_1$. No points will be awarded if $K > K_2$. If $K$ belongs to the interval $[K_1, K_2 + 1]$ the number of awarded points is calculated based on the following formula: $$10 \cdot \frac{K_2 + 1 - K}{K_2 + 1 - K_1} \text{.}$$

Figure 2: Points awared for the test.

테스트

For all the tests used in grading the following constraints are valid: $10 ≤ N ≤ 300$ and $1 ≤ T ≤ 10$. The tests are described in the table below. The starting placement of coins is blurred. Darker pixels represent locations with more copper coins and lighter pixels – locations with more silver coins.

Parameter	Parameter	Parameter
$$T = 1$$ $$N = 10$$ $$K_1 = 17$$ $$K_2 = 17$$	$$T = 2$$ $$N = 50$$ $$K_1 = 576$$ $$K_2 = 576$$	$$T = 3$$ $$N = 300$$ $$K_1 = 18\,657$$ $$K_2 = 20\,540$$
$$T = 4$$ $$N = 300$$ $$K_1 = 21\,839$$ $$K_2 = 23\,547$$	$$T = 5$$ $$N = 300$$ $$K_1 = 17\,169$$ $$K_2 = 18\,746$$	$$T = 6$$ $$N = 300$$ $$K_1 = 20\,873$$ $$K_2 = 22\,346$$
$$T = 7$$ $$N = 300$$ $$K_1 = 21\,477$$ $$K_2 = 22\,656$$	$$T = 8$$ $$N = 300$$ $$K_1 = 19\,614$$ $$K_2 = 20\,153$$	$$T = 9$$ $$N = 300$$ $$K_1 = 20\,777$$ $$K_2 = 21\,095$$
$$T = 10$$ $$N = 300$$ $$K_1 = 20\,150$$ $$K_2 = 22\,609$$