QOJ.ac

QOJ

実行時間制限: 2.0 s メモリ制限: 2048 MB 満点: 100

#15956. 数字金字塔

統計

Uneedtoth 公司是一家为小学生制作数学游戏的公司,Pam D. Monium 刚刚被任命负责他们最新产品:数字金字塔(Number Pyramids)。该游戏由若干卡片组成,每张卡片包含一个由正方形方格组成的金字塔,其中一些方格填有数字,另一些则是空的(见图 1 中最左侧的卡片)。游戏的目标是在每个空方格中填入数值,使得每个方格(最底部的方格除外)中的值都等于其下方两个方格中的值之和。为了让游戏保持“初级”难度,方格中的最终数值必须是绝对值小于 $100$ 的整数(即在 $[-99, 99]$ 范围内)。

卡片的设计还保证了它们可以通过多次遍历卡片来解答。每次遍历从顶行到行底,在每一行中从左到右进行,填入任何可以由其邻居唯一确定的数值。图 1 中其余三张卡片展示了这一过程的一个例子。请注意,可能存在其他方法来解答给定的卡片,但如果使用这种方法无法找到唯一解,则该卡片不应发放给学生。Pam 称这样的卡片为“有歧义的”(ambiguous)。

图 1:样例数字金字塔卡片及一种解法。

对 Pam 来说,事情起初进展顺利,Uneedtoth 工厂的机器源源不断地生产出卡片。但当 Pam 开始进行产品测试时,她发现机器出现了一个故障,导致部分卡片要么存在歧义,要么会导致一个或多个方格出现矛盾的数值。例如,如果图 1 中最左侧的卡片丢失了左下角的 $6$,该卡片就会变得有歧义,因为它会允许多个解;如果该卡片最后一行最右侧的方格是 $5$,或者倒数第二行最右侧的方格是 $3$,这些情况都会导致矛盾,使得卡片无解。最后,如果将 $18$ 改为 $-90$,也将无解,因为求出的其中一个数值会超出 $[-99, 99]$ 的范围。

在 Pam 看来,她现在有两条路可以走。第一条是无视测试直接发货,寄希望于美国孩子们糟糕的数学水平能为她争取足够的时间去寻找另一份工作;或者她可以让人编写软件来检测这些坏卡片并将其剔除。经过一番痛苦的思想斗争并查看了自己的银行账户后,她决定选择后者,并向你寻求帮助。

输入格式

输入首先包含一行一个整数 $n$ ($2 \le n \le 100$),表示金字塔卡片的行数。

接下来有 $n$ 行,指定金字塔的各行。第一行包含一个数值,第二行包含两个数值,依此类推。所有数值 $v$ 均为 $[-99, 100]$ 范围内的整数,其中特殊值 $100$ 表示空方格。

输出格式

输出以下三种情况之一:

  • 如果卡片有多组解且所有数值均在 $[-99, 99]$ 范围内,输出 ambiguous
  • 如果卡片无解,或者解中包含一个或多个超出 $[-99, 99]$ 范围的数值,输出 no solution
  • 否则,输出 solvable,然后按照样例输出的格式输出完整的金字塔。

样例

输入样例 1

6
15
18 100
100 100 -6
100 100 -3 100
100 100 100 -5 100
6 100 100 100 100 100

输出样例 1

solvable
15
18 -3
15 3 -6
9 6 -3 -3
5 4 2 -5 2
6 -1 5 -3 -2 4

输入样例 2

2
100
10 100

输出样例 2

ambiguous

输入样例 3

2
10
10 10

输出样例 3

no solution

输入样例 4

2
100
51 51

输出样例 4

no solution

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.