/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
正整数列 A=(a_1,a_2,\ldots,a_N) が与えられます。
あなたは以下の操作のうち 1 つを選んで行うことを 0 回以上何度でも繰り返せます。
- 1 \leq i \leq N かつ a_i が 2 の倍数であるような整数 i を選び、a_i を \frac{a_i}{2} に置き換える
- 1 \leq i \leq N かつ a_i が 3 の倍数であるような整数 i を選び、a_i を \frac{a_i}{3} に置き換える
あなたの目標は A が a_1=a_2=\ldots=a_N を満たす状態にすることです。
目標を達成するために必要な操作の回数の最小値を求めてください。ただし、どのように操作を行っても目標を達成できない場合、代わりに -1 と出力してください。
制約
- 2 \leq N \leq 1000
- 1 \leq a_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 \ldots a_N
出力
答えを出力せよ。
入力例 1
3 1 4 3
出力例 1
3
次のように操作をすると 3 回で目標を達成でき、これが最小の回数です。
- a_i が 2 の倍数であるような整数 i として 2 を選び、a_2 を \frac{a_2}{2} に置き換える。A は (1,2,3) となる。
- a_i が 2 の倍数であるような整数 i として 2 を選び、a_2 を \frac{a_2}{2} に置き換える。A は (1,1,3) となる。
- a_i が 3 の倍数であるような整数 i として 3 を選び、a_3 を \frac{a_3}{3} に置き換える。A は (1,1,1) となる。
入力例 2
3 2 7 6
出力例 2
-1
どのように操作を行っても目標を達成できません。
入力例 3
6 1 1 1 1 1 1
出力例 3
0
Score : 400 points
Problem Statement
You are given a sequence of positive integers: A=(a_1,a_2,\ldots,a_N).
You can choose and perform one of the following operations any number of times, possibly zero.
- Choose an integer i such that 1 \leq i \leq N and a_i is a multiple of 2, and replace a_i with \frac{a_i}{2}.
- Choose an integer i such that 1 \leq i \leq N and a_i is a multiple of 3, and replace a_i with \frac{a_i}{3}.
Your objective is to make A satisfy a_1=a_2=\ldots=a_N.
Find the minimum total number of times you need to perform an operation to achieve the objective. If there is no way to achieve the objective, print -1 instead.
Constraints
- 2 \leq N \leq 1000
- 1 \leq a_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N a_1 a_2 \ldots a_N
Output
Print the answer.
Sample Input 1
3 1 4 3
Sample Output 1
3
Here is a way to achieve the objective in three operations, which is the minimum needed.
- Choose an integer i=2 such that a_i is a multiple of 2, and replace a_2 with \frac{a_2}{2}. A becomes (1,2,3).
- Choose an integer i=2 such that a_i is a multiple of 2, and replace a_2 with \frac{a_2}{2}. A becomes (1,1,3).
- Choose an integer i=3 such that a_i is a multiple of 3, and replace a_3 with \frac{a_3}{3}. A becomes (1,1,1).
Sample Input 2
3 2 7 6
Sample Output 2
-1
There is no way to achieve the objective.
Sample Input 3
6 1 1 1 1 1 1
Sample Output 3
0