24068번 - XCopy 서브태스크점수다국어

Today, at the end of the programming class, the teacher gave very difficult homework, so the children decided to cheat and copy it from one another. However, they have to work smart in order to not get caught cheating.

The class has $N \times M$ students, placed in $N \times M$ benches on $N$ rows and $M$ columns. Two children are considered neighbours if one sits in a bench adjacent to the left, the right, above or below the bench in which the other one sits. The homework consists of finding a certain non-negative integer. In order for them to not get caught cheating, all these integers must be different. Also, the children are very lazy, therefore they will barely modify their answers when copying them from their neighbours. More precisely, each child’s answer differs by exactly one bit in base $2$ compared to any of his neighbours’ answers. For example $3$ and $2$ differ in exactly one bit, whereas $2$ and $4$ do not.

The children don’t want to raise suspicion, therefore they want the largest answer that any of them gave to be as small as possible. Given $N$ and $M$, create a configuration of answers so that the teacher won’t find out the children cheated.

The input consists of $N$ and $M$ on a single line, separated by a single space.

The output consists of the optimal answers for the children. The output should have $N$ rows, each containing $M$ non-negative integers separated by a single space. These represent the answers for the children, according to where they sit in the class.

• $1 ≤ N, M ≤ 2000$

This task accepts partial solutions, which will be scored partially depending on how close the answer is to the optimal answer, using the following scoring formula: $$S \cdot \max{\left(1 - \sqrt{\frac{\frac{G}{O}-1}{3}}, 0\right)}$$

Where:

• $S$ is the test case’s score,
• $G$ is the given answer,
• $O$ is the optimal answer.

Warning! A solution that does not respect the output format (all numbers are distinct and any $2$ adjacent numbers differ by exactly $1$ bit in the base $2$ representation) will be scored with $0$ on that respective test case.

Within this section, a subscript after a number represents the base in which the number is written. For instance eight may be written as $8_{10} = 1000_2$.

One set of optimal answers for the students are given in the following table:

Observe that between any two adjacent benches the numbers differ with exactly one bit. The maximum value of the solution is $10$, which is the optimal answer. Clearly other solutions are optimal – such as the previous solution but flipped vertically or horizontally.

Another possible partial solution in which the maximum is $15$ is:

This solution would be scored, according to the scoring formula, with $59.1\%$ of the test case score.