#P3195. Generalized Matrioshkas
Generalized Matrioshkas
描述
弗拉基米尔多年来一直致力于制作俄罗斯套娃(matrioshka),这些嵌套玩偶无疑是俄罗斯工艺的真正代表。俄罗斯套娃是一种可以分成两半的玩偶,打开后里面会发现另一个玩偶。然后可以继续打开这个玩偶,里面又有一个玩偶。这个过程可以重复多次,直到最后一个无法再打开的玩偶为止。
最近,弗拉基米尔意识到嵌套玩偶的概念可以推广到嵌套玩具。事实上,他设计了一些玩具,这些玩具可以包含其他玩具,但方式更加灵活。其中一个玩具可以分成两半,并且里面可能有多个玩具。这是弗拉基米尔希望在他的新玩具系列中引入的新特性。
弗拉基米尔开发了一种符号来描述嵌套玩具的构造方式。一个玩具用一个正整数表示,表示其大小。更准确地说:如果打开用表示的玩具,发现里面有表示的玩具,那么必须满足。如果满足这一条件,我们就说玩具直接包含玩具。需要注意的是,任何包含在中的玩具不被视为直接包含在中。
一个广义套娃由一个非零整数序列表示,形式如下:
其中,玩具在序列中用两个整数和表示,负整数在序列中先出现,正整数后出现。
例如,序列
$-9 \quad -7 \quad -2 \quad 2 \quad -3 \quad -2 \quad -1 \quad 1 \quad 2 \quad 3 \quad 7 \quad 9$
表示一个由六个玩具组成的广义套娃,分别是、(两次)、、和。注意,玩具直接包含玩具和。第一个的副本出现在第二个的左侧,而第二个直接包含一个玩具。如果理解为第一个和最后一个配对,则是错误的。
另一方面,以下序列不能描述广义套娃:
$-9 \quad -7 \quad -2 \quad 2 \quad -3 \quad -1 \quad -2 \quad 2 \quad 1 \quad 3 \quad 7 \quad 9$
因为玩具比玩具大,不能放在玩具里面。
$-9 \quad -7 \quad -2 \quad 2 \quad -3 \quad -2 \quad -1 \quad 1 \quad 2 \quad 3 \quad 7 \quad -2 \quad 2 \quad 9$
因为和不能一起放在里面。
$-9 \quad -7 \quad -2 \quad 2 \quad -3 \quad -1 \quad -2 \quad 3 \quad 2 \quad 1 \quad 7 \quad 9$
因为玩具内部存在嵌套问题。
你的任务是编写一个程序,帮助弗拉基米尔区分好的设计和坏的设计。
输入
输入文件包含多个测试用例,每个测试用例占一行。每个测试用例是一个非零整数序列,每个整数的绝对值小于。
输出
对于每个测试用例,输出结果应与输入顺序一致。
如果设计描述了一个广义套娃,则输出:
:-) Matrioshka!
否则,输出:
:-( Try again.
输入数据 1
-9 -7 -2 2 -3 -2 -1 1 2 3 7 9
-9 -7 -2 2 -3 -1 -2 2 1 3 7 9
-9 -7 -2 2 -3 -1 -2 3 2 1 7 9
-100 -50 -6 6 50 100
-100 -50 -6 6 45 100
-10 -5 -2 2 5 -4 -3 3 4 10
-9 -5 -2 2 5 -4 -3 3 4 9
输出数据 1
:-) Matrioshka!
:-( Try again.
:-( Try again.
:-) Matrioshka!
:-( Try again.
:-) Matrioshka!
:-( Try again.
来源
哥伦比亚2006