Description
俄罗斯套娃,大家都知道,就是一种可以分成两半的娃娃,分开之后可以在里面找到另一个小一号的娃娃,一直重复这个操作,直到最后一个娃娃无法被分开了。最近有设计师意识到俄罗斯套娃的创意可以推广到嵌套玩具,所以她设计了一种嵌套型的玩具,与俄罗斯套娃的不同点是,每个娃娃里面可能有不止一个娃娃,同时他开发出一种符号来描述如何构建嵌套娃娃。
每个玩具根据其尺寸大小用一个正整数表示,例如:如果打开一个大小为m的玩具,在其里面的玩具大小分别是n1,n2,…,nr,它们必须满足n1+n2+…+nr< m。此时我们说玩具m直接包含玩具n1,n2,…,nr。应该明确的一点是,那些包含在n1,n2,…,nr里的玩具不算是直接包含在m里的。
一个嵌套玩具可以表示成一个非空的非零整数序列的形式:a1 a2 … aN
玩具k用序列中的两个整数−k和k来表示,负数在前,正数在后。
例如,序列:−9 −7 −2 2 −3 −2 −1 1 2 3 7 9,表示一个嵌套玩具是由六个玩具,即1、2(两个)、3、7和9。
注意,玩具7直接包含了玩具2和3。第一个玩具2是单独一个,第二个玩具2中包含了玩具1。如果把第一个-2是和最后一个2配对就是错误的。
下面的这些序列就不是一个合法的嵌套玩具:
−9 −7 −2 2 −3 −1 −2 2 1 3 7 9,因为玩具2比玩具1大,玩具1是不能包含玩具2的
−9 −7 −2 2 −3 −2 −1 1 2 3 7 −2 2 9,因为7和2不可能同时放在9中
−9 −7 −2 2 −3 −1 −2 3 2 1 7 9 ,因为玩具3存在不合法的嵌套
你的任务是编写一个程序来判断哪些序列是合法的,哪些是不合法的。
Input
输入包含多组测试数据,每组测试数据一行。每组测试数据是一个非零的整数序列,每一个数的绝对值小于10^7
Output
对于每组测试数据输出一行,如果序列是合法的则输出:-) Matrioshka!,如果序列是不合法的则输出:-( Try again.
-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
:-) Matrioshka!
:-( Try again.
:-( Try again.
:-) Matrioshka!
:-( Try again.
:-) Matrioshka!
:-( Try again.