Problem F: 寻找砝码集
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$18$ |
正确数量 |
$5$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
贪心 |
当前分类(单击移除)：
贪心
单击选择分类：
现有重量为w1, w2, w3,...,wn的n种物品，你需要找到一组物品集合作为砝码集，使得这n种物品每件都能被这个砝码集在天平上称量，并且使这个砝码集中含有的物品种类数量最小。
物品w能被砝码集y称量的意思是指：把物品w放在天平的左边，然后从砝码集y中选取一些物品，每件物品任意放在天平左边或者右边，最终使得天平平衡。这个过程中你可以使用组成砝码集y的每种物品任意多次。
有多组测试数据。
每组数据有两行，
第一行是一个整数n(1 <= n <= 50)，
第二行包含n个整数w1,w2,...,wn( 1 <= wi <= 10000000 )，表示这n种物品的重量，
输入以一个0结束。
输出一个正整数，代表这个砝码集中含有的物品种类数量。
4
5 4 1 8
4
2 3 8 9
3
13 5 11
0