#1473. 「THUPC 2021 初赛」棋盘

「THUPC 2021 初赛」棋盘

题目描述

有一个 nnmm 列的棋盘,共有 nmn m 个格子。请你在格子内放入棋子(每个格子可以放入至多一个棋子),使得对于所有 1im1 \le i \le m,第 ii 列里恰好包含 aia_i 个棋子。另外,棋盘上的任意两颗棋子都不能边相邻。

请判断是否存在一种合法方案。如果存在,请输出任意一个合法方案。

输入格式

输入的第一行包含两个正整数 n,mn, m,保证 n300,m300n \le 300, m \le 300
输入的第二行包含 mm 个非负整数 a1,a2,,ama_1, a_2, \ldots , a_m,保证 0ain0 \le a_i \le n

输出格式

如果无解,输出一个字符串 No
如果有解,第一行输出一个字符串 Yes,接下来 nn 行每行输出一个长度为 mm 的字符串,表示你构造的棋盘方案。其中 0 表示空格,1 表示放入棋子的格子。

样例 1

3 4
2 1 2 1

Yes
1010
0101
1010

3 4
2 3 3 3

No

来源

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2021)初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。