Putting Plates (Codeforces 1544B)
Tags: Others, constructive algorithms

To celebrate your birthday you have prepared a festive table! Now you want to seat as many guests as possible.The table can be represented as a rectangle with height $$$h$$$ and width $$$w$$$, divided into $$$h \times w$$$ cells. Let $$$(i, j)$$$ denote the cell in the $$$i$$$-th row and the $$$j$$$-th column of the rectangle ($$$1 \le i \le h$$$; $$$1 \le j \le w$$$).Into each cell of the table you can either put a plate or keep it empty.As each guest has to be seated next to their plate, you can only put plates on the edge of the table — into the first or the last row of the rectangle, or into the first or the last column. Formally, for each cell $$$(i, j)$$$ you put a plate into, at least one of the following conditions must be satisfied: $$$i = 1$$$, $$$i = h$$$, $$$j = 1$$$, $$$j = w$$$.To make the guests comfortable, no two plates must be put into cells that have a common side or corner. In other words, if cell $$$(i, j)$$$ contains a plate, you can't put plates into cells $$$(i - 1, j)$$$, $$$(i, j - 1)$$$, $$$(i + 1, j)$$$, $$$(i, j + 1)$$$, $$$(i - 1, j - 1)$$$, $$$(i - 1, j + 1)$$$, $$$(i + 1, j - 1)$$$, $$$(i + 1, j + 1)$$$.Put as many plates on the table as possible without violating the rules above.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.Each of the following $$$t$$$ lines describes one test case and contains two integers $$$h$$$ and $$$w$$$ ($$$3 \le h, w \le 20$$$) — the height and the width of the table.

Output: For each test case, print $$$h$$$ lines containing $$$w$$$ characters each. Character $$$j$$$ in line $$$i$$$ must be equal to $$$1$$$ if you are putting a plate into cell $$$(i, j)$$$, and $$$0$$$ otherwise. If there are multiple answers, print any.All plates must be put on the edge of the table. No two plates can be put into cells that have a common side or corner. The number of plates put on the table under these conditions must be as large as possible.You are allowed to print additional empty lines.

Note: For the first test case, example output contains the only way to put $$$6$$$ plates on the table.For the second test case, there are many ways to put $$$4$$$ plates on the table, example output contains one of them.Putting more than $$$6$$$ plates in the first test case or more than $$$4$$$ plates in the second test case is impossible.

Sample Inputs:
3
3 5
4 4
5 6

Sample Outputs:
10101
00000
10101

0100
0001
1000
0010

010101
000000
100001
000000
101010

Solution (Python):
from math import ceil

def solve():
    (h, w) = map(int, input().split())
    result = str()
    void_str = '0' * w + '\n'
    top_str = '10' * (w // 2)
    if w % 2 == 1:
        top_str += '1'
    top_str += '\n'
    if h % 2 == 0:
        bottom_str = '0' * w
    else:
        bottom_str = '10' * (w // 2)
        if w % 2 == 1:
            bottom_str += '1'
    bottom_str += '\n'
    middle_str = '1' + '0' * (w - 2) + '1\n'
    result += top_str
    if h % 2 == 0:
        for i in range(2, h - 1):
            if i % 2 == 0:
                result += void_str
            else:
                result += middle_str
        result += void_str
        result += top_str
    else:
        for i in range(2, h):
            if i % 2 == 0:
                result += void_str
            else:
                result += middle_str
        result += bottom_str
    print(result.strip())

def main():
    for _ in range(int(input())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
t = int(input())

def solve(h, w):
    M = [0] * h
    for i in range(h):
        M[i] = [0] * w
    for i in range(h):
        for j in range(w):
            if i == 0 or i == h - 1:
                if j % 2 == 0:
                    M[i][j] = 1
                continue
            if i % 2 == 0 and i + 1 < h - 1:
                if j == 0 or j == w - 1:
                    M[i][j] = 1
    for row in M:
        s = ''
        for i in row:
            s += str(i)
        print(s)
for _ in range(t):
    (h, w) = map(int, input().split())
    solve(h, w)

Solution (Python):
def solve(h, w, shift):
    p = list(((i, 1) for i in range(1, h + 1)))
    p += list(((h, j) for j in range(1, w + 1)))
    p += list(((i, w) for i in range(h, 0, -1)))
    p += list(((1, j) for j in range(w, 0, -1)))
    s = p[shift]
    ans = [s]
    for c in p[shift:]:
        if max(abs(c[0] - s[0]), abs(c[1] - s[1])) <= 1 or max(abs(c[0] - ans[-1][0]), abs(c[1] - ans[-1][1])) <= 1:
            continue
        else:
            ans += [c]
    return ans
nt = int(input())
for tt in range(nt):
    (h, w) = map(int, input().split())
    ans = []
    for shift in range(4):
        c1 = solve(h, w, shift)
        if len(c1) > len(ans):
            ans = c1
    res = [['0'] * w for i in range(h)]
    for p in ans:
        res[p[0] - 1][p[1] - 1] = '1'
    for x in res:
        print(''.join(x))
    print()