#P1457. Lord of the Ring

Lord of the Ring

描述
佛罗多必须完成一项崇高而艰巨的任务:他必须摧毁一枚具有魔力的邪恶戒指。在这场冒险中,他必须前往一个名为魔多的危险之地,并将戒指扔进一处火焰裂隙。他已经离开家乡有一段时间了,目前正沿着一条笔直且相当长的道路前行,沿途零星分布着灌木丛。由于疲惫不堪,佛罗多认为自己最好休息一下。这条路上唯一安全的地方是某片灌木丛,其位置可通过一个魔法公式计算得出,而该公式需要用到数值PP——PP是道路上相邻灌木丛之间距离的乘积。不幸的是,佛罗多只知道所有灌木丛两两之间的距离,以及这个魔法公式,但他不知道PP的值。你能在这方面帮助他吗?

输入
程序从标准输入读取数据。每个数据集对应佛罗多所走道路上灌木丛两两之间的一组距离。每个数据集以距离的数量开头,随后是按非递减顺序排列的距离值。输入中可以自由出现空白字符。

已知道路上至少有2棵灌木丛,最多有1000棵灌木丛。此外,PP的值不会超过10910^9

输出
对于每组数据,程序应将计算出的PP值输出到标准输出,每个结果占单独一行。如果无法从该数据集推导出PP,则输出“No solution”。

输入数据 1

6  
1 2  2   3  3 5  

3  
1 2 2

输出数据 1

4  
No solution

提示
第二组数据不存在解。无法从给定数据推导出道路上灌木丛的位置,因此无法计算相邻点之间的距离。

来源
东南欧 2003年