← 返回题目列表

AtCoder · abc100_c

C. *3 或 /2

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

由于 AtCoder 初学者竞赛 100 正在进行,AtCoder, Inc. 的办公室装饰有一系列长度 N, a = {a_1, a_2, a_3, ..., a_N}.
Snuke,一名员工,想玩这个序列。

具体来说,他想尽可能多次地重复以下操作:

For every i satisfying 1 \leq i \leq N, perform one of the following: "divide a_i by 2" and "multiply a_i by 3".  
Here, choosing "multiply a_i by 3" for every i is not allowed, and the value of a_i after the operation must be an integer.

最多可以执行多少次操作?

约束

  • N 是介于 1 和 10 \ 000 (含)。
  • a_i 是介于 1 和 1 \ 000 \ 000 \ 000 (含)。

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 a_3 ... a_N

输出

打印 Snuke 可以执行的最大操作数。


示例输入 1

3
5 2 4

示例输出 1

3

序列最初是 {5, 2, 4}。可以进行如下三种操作:

  • 首先,乘以 a_1 by 3,乘以 a_2 by 3 并除以 a_3 by 2。现在的顺序是 {15, 6, 2}.
  • 接下来,乘以 a_1 by 3, 除 a_2 by 2 并乘以 a_3 by 3。现在的顺序是 {45, 3, 6}.
  • 最后,乘以 a_1 by 3,乘以 a_2 by 3 并除以 a_3 by 2。现在的顺序是 {135, 9, 3}.

示例输入 2

4
631 577 243 199

示例输出 2

0

由于所有元素都是奇数,因此无法执行任何操作。因此,答案是 0.


示例输入 3

10
2184 2126 1721 1800 1024 2528 3360 1945 1280 1776

示例输出 3

39