CodeForces 1118C Palindromic Matrix

Palindromic Matrix

time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output

Input The first line contains one integer n (1≤n≤20).

The second line contains n2 integers a1,a2,…,an2 (1≤ai≤1000) — the numbers to put into a matrix of n rows and n columns.

Output If it is possible to put all of the n2 numbers into a matrix of n rows and n columns so that each number is used exactly once, each cell contains exactly one number and the resulting matrix is palindromic, then print “YES”. Then print n lines with n space-separated numbers — the resulting matrix.

If it’s impossible to construct any matrix, then print “NO”.

You can print each letter in any case (upper or lower). For example, “YeS”, “no” and “yES” are all acceptable.

Examples input

4 1 8 8 1 2 2 2 2 2 2 2 2 1 8 8 1

output

YES 1 2 2 1 8 2 2 8 8 2 2 8 1 2 2 1

input

3 1 1 1 1 1 3 3 3 3

output

YES 1 3 1 3 1 3 1 3 1

input

4 1 2 1 9 8 4 3 8 8 3 4 8 9 2 1 1

output

NO

input

1 10

output

YES 10

解题方法: 给每个输入的数计数,取n/2为每个1/4矩阵的长,如果n为奇数,则还要增加两条中间的数,每条长度也为n/2, 构造1/4矩阵然后通过翻转得到完整的矩阵,每次从数组里取数,1/4矩阵每个位置的数都要是4个(因为要翻转得到完整矩阵),因此每次取4个数,取到达到n/2个为止,奇数的话要继续取两条链,每条长度为n/2,且每个数至少有一个,然后剩下的最后一个数为中心 上述取数过程中出现任意一次取不到数,则表示无法构造矩阵,输出NO,退出即可

代码如下:

class Solution(): def __init__(self): n = int(input()) num = [] mat = [] res = [] for i in range(0, 1001): num.append(0) m = input().split() for i in range(n * n): if num[int(m[i])] == 0: res.append(int(m[i])) num[int(m[i])] += 1 len = int(n / 2) f = True for i in range(len): for j in range(len): f = False for k in res: if num[k] >= 4: num[k] -= 4; mat.append(k) f = True break if not f: print('No') return if n & 1: colum = [] row = [] for i in range(len): f = False for k in res: if num[k] >= 2: num[k] -= 2 colum.append(k) f = True break if not f: print('No') return for i in range(len): f = False for k in res: if num[k] >= 2: num[k] -= 2 row.append(k) f = True break if not f: print('No') return center = -1 for i in res: if num[i] == 1: num[i] = 0 center = i break if center == -1: print('No') return print('Yes') for i in range(len): for j in range(len * i, len * i + len): print(mat[j], end=' ') k = len * i + len - 1 print(colum[i], end=' ') for j in range(len): print(mat[k], end='') if j == len - 1: print() else: print(end=' ') k -= 1 i = len - 1 for j in row: print(j, end=' ') print(center, end='') for j in row: print(' ' + str(row[i]), end='') i -= 1 print() l = len - 1 for i in range(len): result=[] for j in range(len * len - (i + 1) * len, len * len - (i + 1) * len + len): result.append(mat[j]) print(mat[j], end=' ') k = len-1 print(colum[l], end=' ') l -= 1 for j in range(len): print(result[k],end='') if j == len - 1: print() else: print(end=' ') k -= 1 else: print('Yes') for i in range(len): for j in range(len * i, len * i + len): print(mat[j], end=' ') k = len * i + len - 1 for j in range(len): print(mat[k], end='') if j == len - 1: print() else: print(end=' ') k -= 1 l = len - 1 for i in range(len): for j in range(len*len - len * i - len, len*len - len * i): print(mat[j], end=' ') k = len*len - len * i - 1 for j in range(len): print(mat[k], end='') if j == len - 1: print() else: print(end=' ') k -= 1 if __name__ == '__main__': Solution()