#2185. 菱形覆盖

菱形覆盖

菱形覆盖

题目描述

标题: 菱形覆盖 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

题目描述

给一个边长为 n 的正三角形,其被分成了 n2 个小的边长为 1 的正三角形,其中有 n(n+1)2 个正着的, n(n−1)2 个倒着的。现在有 n 个正着的三角形被切掉了,剩下 n(n−1)2 个正着的和 n(n−1)2 个倒着的。问能否用 n(n−1)2 个夹角为 60∘ 和 120∘ ,边长为 1 的菱形覆盖所有小三角形。如果有,输出一种方案。

一个边长为 4 的正三角形 三种不同的菱形,从左到右标号为 1,2,3

一种 n=4 的例子

输入格式

第一行一个正整数 n ,代表大正三角形的边长。

接下来 n 行,第 i(2≤i≤n+1) 行一个长度为 i−1 的 01 字符串,第 j 个字符为 0 代表第 i 行第 j 个正着的小三角形被切掉了。

输出格式

如果没有一种合法的菱形覆盖的方式,输出 Impossible! 。

否则输出任意一组合法解。合法解一共包含 n 行,第 i 行为一个长度为 i 的字符串,第 i 行第 j 个字符表示第 i 行第 j 个正着的小三角形的情况,具体格式如下:

  • 如果第 i 行第 j 个字符为 ′−′,代表这个小三角形被切掉了。
  • 如果第 i 行第 j 个字符为 ′1′,代表这个小三角形被第一种菱形覆盖。
  • 如果第 i 行第 j 个字符为 ′2′,代表这个小三角形被第二种菱形覆盖。
  • 如果第 i 行第 j 个字符为 ′3′,代表这个小三角形被第三种菱形覆盖。

样例输入

4
0
11
010
1101

样例输出

-
21
-3-
33-1

数据范围

保证 n≤5000 。

subtask1(5pts) : n≤5 。

subtask2(10pts) : n≤10 。

subtask3(35pts) : n≤500 。

subtask4(5pts) :保证每一行恰好有一个正着的小三角形被切掉。

subtask5(15pts) :保证存在一组解。

subtask6(30pts) :无特殊限制。

时间限制:2s

空间限制:1GB

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4
0
11
010
1101
-
21
-3-
33-1