谁可以用c++解释一下?
真假金币 查看测评数据信息
小C是个探险家,在金银岛上找到了许多宝藏,其中就有n袋金币,每袋金币数量为a_i。可是后来有坏人把其中几袋换成假币了,经过检查后发现每袋金币要么全是真币(每个重5克),要么全是假币(每个重4克)。
如果现在只有一台电子秤,n袋金币依次排列,你可以从每袋金币中挑出若干枚进行一次称量(也可以一枚都不选),若要确定前1,2,……,n袋金币的真假,至少要称量几次呢?
输入格式
第一行一个整数n,表示有n袋金币。
接下来一行n个整数a_i,表示每袋金币的数量。
输出格式
n行,每行一个整数,第i行表示想要确定前i袋金币的真假至少要称量几次。
输入/输出例子1
输入:
3
2 3 4
输出:
1
1
1
样例解释
以前三袋硬币为例,分别取出1、2、4枚硬币,则一次称量的结果即可确定三袋的真假。
对于10%的数据,n≤1
对于30%的数据,n≤2
对于60%的数据,n≤100
对于80%的数据,n≤1000
对于100%的数据,n≤10^5,a_i≤10^9
存在10%的数据,a_i=1