DMOPC '20 Contest 5 P5 - Slacking Off Again

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

After counting patterns on his N-pixel-high by M-pixel-wide computer screen, Bob is getting bored again. So this time, he decides to tamper with the screen. He wants to colour each pixel either yellow (by lighting it up) or black (by keeping it unlit).

Bob thinks a rectangle of pixels, with both dimensions at least 2, is ugly if its first and last rows are identical and its first and last columns are identical. (Note: this definition is the same as the one in Problem 4.) For example, the following rectangles are ugly:

Please help Bob colour the N \times M screen in a way that contains the fewest ugly sub-rectangles possible!


2 \le N, M

4 \le N \times M \le 200\,000

Subtask 1 [10%]

N, M \le 4

Subtask 2 [10%]

N \le 4

M \le 30

Subtask 3 [20%]

N, M \le 30

Subtask 4 [30%]

N, M \le 100

Subtask 5 [30%]

No additional constraints.

Input Specification

The first and only line contains two space-separated integers, N and M.

Output Specification

Output an N \times M grid of characters—Y for yellow and B for black—representing a colouring that contains a minimal number of ugly sub-rectangles. If there are multiple such colourings possible, you may output any one of them.

Sample Input

3 3

Sample Output



There are no comments at the moment.