Divide by 2 or 3

题目描述

给出一个正整数序列：$A=(a_1,a_2,\ldots,a_N)$。
你可以任意次（包括零次）选择并执行下面的操作之一。

选择一个整数 $i$ 满足 $1 \leq i \leq N$ 且 $a_i$ 可被 $2$ 整除，将 $a_i$ 替换为 $\frac{a_i}{2}$。 选择一个整数 $i$ 满足 $1 \leq i \leq N$ 且 $a_i$ 可被 $3$ 整除，将 $a_i$ 替换为 $\frac{a_i}{3}$。

你的目标是使得 $A$ 满足 $a_1=a_2=\ldots=a_N$。
找出达到目标所需执行操作的最少总次数。如果无法达到目标，则输出 $-1$。

输入格式

输入从标准输入按以下格式给出： $N$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

输出答案。

3
1 4 3

3

3
2 7 6

-1

6
1 1 1 1 1 1

0

提示

$2 \leq N \leq 1000$ $1 \leq a_i \leq 10^9$ 输入中的所有值均为整数。下面是一种用三次操作达到目标的方法，这也是所需的最少次数。

选择一个整数 $i=2$ 且 $a_i$ 可被 $2$ 整除，将 $a_2$ 替换为 $\frac{a_2}{2}$。$A$ 变为 $(1,2,3)$。 选择一个整数 $i=2$ 且 $a_i$ 可被 $2$ 整除，将 $a_2$ 替换为 $\frac{a_2}{2}$。$A$ 变为 $(1,1,3)$。 选择一个整数 $i=3$ 且 $a_i$ 可被 $3$ 整除，将 $a_3$ 替换为 $\frac{a_3}{3}$。$A$ 变为 $(1,1,1)$。
没有办法达到目标。

标签: AtCoder|abc276D

来源

AtCoder|abc276D