P1032 - Divide by 2 or 3

Memory Limit：1024 MB Time Limit：2.000 S

Judge Style：Text Compare Creator：

Submit：22 Solved：10

Submit Submit Record Statistics ShowOff!

You are given a sequence of positive integers: $lns="http://www.w3.org/1998/Math/MathML"> � = (�_{1}, �_{2}, \dots, �_{�})$ .
You can choose and perform one of the following operations any number of times, possibly zero.

Choose an integer $lns="http://www.w3.org/1998/Math/MathML"> �$ such that $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq � \leq �$ and $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ is a multiple of $lns="http://www.w3.org/1998/Math/MathML"> 2$ , and replace $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ with $lns="http://www.w3.org/1998/Math/MathML"> \frac{�_{�}}{2}$ .
Choose an integer $lns="http://www.w3.org/1998/Math/MathML"> �$ such that $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq � \leq �$ and $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ is a multiple of $lns="http://www.w3.org/1998/Math/MathML"> 3$ , and replace $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ with $lns="http://www.w3.org/1998/Math/MathML"> \frac{�_{�}}{3}$ .

Your objective is to make $lns="http://www.w3.org/1998/Math/MathML"> �$ satisfy $lns="http://www.w3.org/1998/Math/MathML"> �_{1} = �_{2} = \dots = �_{�}$ .
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.

The input is given from Standard Input in the following format:

$N$

 $a_{1}$   $lns="http://www.w3.org/1998/Math/MathML"> �_{2}$   $lns="http://www.w3.org/1998/Math/MathML"> \dots$   $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$

$2 \leq N \leq 1000$
$lns="http://www.w3.org/1998/Math/MathML"> 1 \leq �_{�} \leq 1 0^{9}$
All values in the input are integers.

Print the answer.

3
1 4 3

Here is a way to achieve the objective in three operations, which is the minimum needed.

Choose an integer $lns="http://www.w3.org/1998/Math/MathML"> � = 2$ such that $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ is a multiple of $lns="http://www.w3.org/1998/Math/MathML"> 2$ , and replace $lns="http://www.w3.org/1998/Math/MathML"> �_{2}$ with $lns="http://www.w3.org/1998/Math/MathML"> \frac{�_{2}}{2}$ . $lns="http://www.w3.org/1998/Math/MathML"> �$ becomes $lns="http://www.w3.org/1998/Math/MathML"> (1, 2, 3)$ .
Choose an integer $lns="http://www.w3.org/1998/Math/MathML"> � = 2$ such that $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ is a multiple of $lns="http://www.w3.org/1998/Math/MathML"> 2$ , and replace $lns="http://www.w3.org/1998/Math/MathML"> �_{2}$ with $lns="http://www.w3.org/1998/Math/MathML"> \frac{�_{2}}{2}$ . $lns="http://www.w3.org/1998/Math/MathML"> �$ becomes $lns="http://www.w3.org/1998/Math/MathML"> (1, 1, 3)$ .
Choose an integer $lns="http://www.w3.org/1998/Math/MathML"> � = 3$ such that $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ is a multiple of $lns="http://www.w3.org/1998/Math/MathML"> 3$ , and replace $lns="http://www.w3.org/1998/Math/MathML"> �_{3}$ with $lns="http://www.w3.org/1998/Math/MathML"> \frac{�_{3}}{3}$ . $lns="http://www.w3.org/1998/Math/MathML"> �$ becomes $lns="http://www.w3.org/1998/Math/MathML"> (1, 1, 1)$ .

Atcoder

Submit Submit Record Statistics ShowOff!

1032: Divide by 2 or 3

Description

Input

Output

Sample Input Copy

Sample Output Copy

HINT

Source/Category