九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1395-九度Online Judge,用代码记录你的成长之路!

题目1395:爱钱的胡老板

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:601

解决:152

题目描述:

胡老板,别名浩帆,是九度技术组中最喜欢钱的一个,当然了,他钱肯定是没多少的,但是他唯一的乐趣也就是把玩手中不多的钱了。

胡老板难得出了趟国(当然了,也就越南老挝东南亚了,前面说了,他钱不多)。

在A国,他发现了一台自动兑换货币的机器。这时,他爱钱的兴趣又体现出来了,他想通过兑换一定数量的钱,来保证换取这个国家的所有种类的硬币。但是,这种自动兑换机的兑换策略并不知道,所以胡老板想让你帮忙计算下,是否存在这么一种可能,通过兑换一定数量的纸币,能够保证一定获取所有可能的硬币,假如存在,则只需要告诉胡老板其最小值;假如不存在,就输出-1。

例如,A国有2、5这两种面额的硬币,那么我们只需要兑换7面额的纸币即可保证获取2和5这两种面额的硬币;同样,若B国有1、2这两种面额的硬币,那我们就无能为力了,因为所有的面额,可能都是由面额为1的硬币组成。

输入:

每个测试案例包括两行:

第一行为整数N,代表硬币的种类,其中1 <= N <= 50。

第二行为N个大于0小于等于10000的整数,代表硬币的面额。注意,不同种类的硬币,面额也可能一样。

输出:

对于每个测试案例,输出一行:

若方案存在,则输出一个最小的值;若不存在,则输出-1。

样例输入:
2
2 5
2
1 2
2
1 1
样例输出:
7
-1
-1
答疑:
解题遇到问题?分享解题心得?讨论本题请访问:http://t.jobdu.com/thread-8118-1-1.html