#1002. 【基础】天平

【基础】天平

说明

小 T 到 CZ 中学上的第一堂课是物理课,第一堂课 L 老师就把大家带到创新实验室去 做实验了,实验的内容是天平称物。众所周知天平是物理实验室中的一种衡量物体质量的 仪器,它依据杠杆原理制成,在杠杆的两端各有一个小盘,一端放砝码,另一端放要称的 物体,杠杆中央装有指针,两端平衡时,意味着两端的质量相等。这些道理对学过初中物 理的人来说已经是老生常谈了,小T原以为这次实验跟初二做过的不会有太大区别,但当 他一走进创新实验室,就立即被眼前堆得跟小山一样的砝码震住了,小T走上前去拿出几 个砝码看了一下,发现所有砝码上标明的质量均为 2 的幂次:1g,2g,4g,8g,16g,32g 等等, 这下小T彻底被雷到了,心想这是物理实验室吗?怎么跟计算机中的二进制表示那么相似 呢? 正当小 T 想得出神,L 老师已经在大声催促同学们座到指定位置上去做实验了,小 T 和同桌小S两人一组很快就把桌上几个物体的质量用天平称出来了,抬头一看周围的同学 还都在忙碌着,小 T 就对小 S 说:“我们来做个游戏好不好?”小 S 说:“做什么游戏?” 小T说:“很简单,我随意抓一把些砝码放到天平的左端,你要在天平的右端放置最少数 量的砝码使得天平平衡。”小 S 说:“没问题,那我们就开始吧!”游戏开始后,小S发现 当小T放上去的砝码个数较多且相同质量的砝码有多个时有点难办,于是他就找到了会编程的你,希望你帮他处理这个问题。

输入格式

输入数据共有两行,第一行包含一个正整数 N,表示小 T 一共抓了 N 个砝码放到了天 平的左端。

第二行有 N 个用空格隔开的正整数 表示每个砝码的质量,每个砝码的质量都是 2 的幂次,即等于若干个 2 连乘的积,如 8 等于 3 个 2 连乘的积,64 等于 6 个 2 连乘的积,1024 等于 10 个 2 连乘的积等等,特别地我们规定 1 也是 2 的幂次。

输出格式

输出数据仅有一行包含一个正整数表示小 S 最少要在天平的右端放置几个砝码,CZ 中 学的物理创新实验室里只有质量为 2 的幂次的砝码,并且每种砝码都取之不尽用之不竭。

样例

输入1  
2
8 8

输入2 6 1 1 1 4 1 1

输出1
1</p>

输出2 2

</p>

提示

【样例解释】

样例 1 中小 T 抓了两个 8g 的砝码放到了天平的左端,小 S 只要将一个 16g 的砝码放 到天平的右端就行了,答案为 1;样例 2 中小 T 抓了 5 个 1g 的砝码和 1 个 4g 的砝码放到 了天平的左端,小 S 只要将一个 8g 的砝码和一个 1g 的砝码放到天平的右端就行了,答案 为   2,可以验证放一个砝码到天平的右端是不可能平衡的,因为创新实验室里不存在质量 为 9g 的砝码,9 不是 2 的幂次。上文中的 g 是质量的单位,翻译成中文叫“克”,1 千克 就是我们平时讲的 1 公斤。

【数据范围】

30%的数据满足:N≤10,天平左端的 N 个砝码的总质量不超过 100g

60%的数据满足:N≤100,天平左端的 N 个砝码的总质量不超过 10000g

100%的数据满足:N≤10000,天平左端的 N 个砝码的总质量不超过 2000000000g

【来源】

2014年常州市赛