#P3195. Generalized Matrioshkas

Generalized Matrioshkas

描述

弗拉基米尔多年来一直致力于制作俄罗斯套娃(matrioshka),这些嵌套玩偶无疑是俄罗斯工艺的真正代表。俄罗斯套娃是一种可以分成两半的玩偶,打开后里面会发现另一个玩偶。然后可以继续打开这个玩偶,里面又有一个玩偶。这个过程可以重复多次,直到最后一个无法再打开的玩偶为止。

最近,弗拉基米尔意识到嵌套玩偶的概念可以推广到嵌套玩具。事实上,他设计了一些玩具,这些玩具可以包含其他玩具,但方式更加灵活。其中一个玩具可以分成两半,并且里面可能有多个玩具。这是弗拉基米尔希望在他的新玩具系列中引入的新特性。

弗拉基米尔开发了一种符号来描述嵌套玩具的构造方式。一个玩具用一个正整数表示,表示其大小。更准确地说:如果打开用mm表示的玩具,发现里面有n1,n2,,nrn_1, n_2, \ldots, n_r表示的玩具,那么必须满足n1+n2++nr<mn_1 + n_2 + \ldots + n_r < m。如果满足这一条件,我们就说玩具mm直接包含玩具n1,n2,,nrn_1, n_2, \ldots, n_r。需要注意的是,任何包含在n1,n2,,nrn_1, n_2, \ldots, n_r中的玩具不被视为直接包含在mm中。

一个广义套娃由一个非零整数序列表示,形式如下:

a1a2aNa_1 \quad a_2 \quad \ldots \quad a_N

其中,玩具kk在序列中用两个整数k-kkk表示,负整数在序列中先出现,正整数后出现。

例如,序列

$-9 \quad -7 \quad -2 \quad 2 \quad -3 \quad -2 \quad -1 \quad 1 \quad 2 \quad 3 \quad 7 \quad 9$

表示一个由六个玩具组成的广义套娃,分别是1122(两次)、337799。注意,玩具77直接包含玩具2233。第一个22的副本出现在第二个22的左侧,而第二个22直接包含一个玩具11。如果理解为第一个2-2和最后一个22配对,则是错误的。

另一方面,以下序列不能描述广义套娃:

$-9 \quad -7 \quad -2 \quad 2 \quad -3 \quad -1 \quad -2 \quad 2 \quad 1 \quad 3 \quad 7 \quad 9$

因为玩具22比玩具11大,不能放在玩具11里面。

$-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$

因为7722不能一起放在99里面。

$-9 \quad -7 \quad -2 \quad 2 \quad -3 \quad -1 \quad -2 \quad 3 \quad 2 \quad 1 \quad 7 \quad 9$

因为玩具33内部存在嵌套问题。

你的任务是编写一个程序,帮助弗拉基米尔区分好的设计和坏的设计。

输入

输入文件包含多个测试用例,每个测试用例占一行。每个测试用例是一个非零整数序列,每个整数的绝对值小于10710^7

输出

对于每个测试用例,输出结果应与输入顺序一致。
如果设计描述了一个广义套娃,则输出:

:-) 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