Ta có một ma trận gồm các ô vuông với \(R\) hàng và \(C\) cột. Cần vẽ một đường chéo trong mỗi ô. Mỗi ô phải chứa đúng một trong hai đường chéo có thể có: đường chéo xuôi /, nối góc dưới trái với góc trên phải của ô, hoặc đường chéo ngược \, nối góc trên trái với góc dưới phải.

Với mỗi hàng và mỗi cột, ta muốn vẽ một số lượng cụ thể đường chéo của từng loại. Ngoài ra, sau khi vẽ xong, ma trận phải không có hình vuông (square free), nghĩa là không được tồn tại hình vuông nào tạo bởi các đường chéo đã thêm.

Ví dụ, giả sử ma trận có \(4\) hàng và \(4\) cột. Số bên cạnh mỗi hàng là số đường chéo / chính xác phải có trong hàng đó. Số bên dưới mỗi cột là số đường chéo / chính xác phải có trong cột đó.

Có nhiều cách điền ma trận mà vẫn tôn trọng những số lượng theo hàng và cột ấy. Dưới đây là ba khả năng:

Hai ma trận đầu không square free, còn ma trận thứ ba thì có. Trong ma trận đầu tiên, có một hình vuông với cạnh dài bằng \(2\) đường chéo, các đỉnh nằm ở trung điểm bốn cạnh của ma trận. Trong ma trận thứ hai, có một hình vuông cạnh dài bằng \(1\) đường chéo ở góc dưới bên phải. Trong ma trận thứ ba không có hình vuông nào. Vì thế, ma trận thứ ba là một cách vẽ hợp lệ theo mọi quy tắc.

Cho kích thước ma trận và số đường chéo / chính xác phải vẽ trong mỗi hàng và mỗi cột, hãy tạo ra một ma trận square free thỏa các ràng buộc hàng và cột, hoặc thông báo rằng không tồn tại ma trận như vậy.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test gồm đúng ba dòng. Dòng đầu chứa \(R,C\), là số hàng và số cột của ma trận. Dòng thứ hai chứa \(R\) số nguyên \(S_1,S_2,\ldots,S_R\); \(S_i\) là số đường chéo / chính xác phải vẽ trong hàng thứ \(i\) tính từ trên xuống. Dòng thứ ba chứa \(C\) số nguyên \(D_1,D_2,\ldots,D_C\); \(D_i\) là số đường chéo / chính xác phải vẽ trong cột thứ \(i\) tính từ trái sang.

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là IMPOSSIBLE nếu không có ma trận đã điền nào tuân theo mọi quy tắc, và là POSSIBLE trong trường hợp ngược lại. Nếu in POSSIBLE, hãy in thêm \(R\) dòng, mỗi dòng gồm \(C\) ký tự. Ký tự thứ \(j\) trên dòng thứ \(i\) phải là / nếu ô ở hàng thứ \(i\) từ trên xuống, cột thứ \(j\) từ trái sang trong ma trận đề xuất chứa đường chéo xuôi; nếu không thì phải là \. Ma trận đề xuất phải hợp lệ theo mọi quy tắc.

Ràng buộc

• \(1\le T\le100\).
• \(0\le S_i\le C\) với mọi \(i\).
• \(0\le D_i\le R\) với mọi \(i\).

Phân nhóm

Phân nhóm 1 (phản hồi hiện)

• \(2\le R\le6\).
• \(2\le C\le6\).

Phân nhóm 2 (phản hồi ẩn)

• \(2\le R\le20\).
• \(2\le C\le20\).

Điểm các phân nhóm

Ví dụ

4
4 4
3 2 3 3
3 3 2 3
2 3
1 1
1 1 1
2 3
1 2
1 1 1
3 3
2 0 2
2 0 2

Case #1: POSSIBLE
//\/
\/\/
///\
/\//
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
\\/
//\
Case #4: POSSIBLE
/\/
\\\
/\/

Nguồn

Google Code Jam 2021, Vòng 3, bài Square Free.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.