34771번 - Collatz polynomial 다국어

문제

Everyone knows (or has heard of) the famous Collatz Conjecture: take a positive integer. If it is odd, multiply by 3ドル$ and add 1ドル$. If it is even, divide by 2ドル$. Repeat the process until you reach 1ドル$. Despite its simplicity, no one knows how to prove whether the sequence really always reaches 1ドル,ドル regardless of the initial number.

Aline, a fan of this type of curiosity, decided to create a variation using polynomials instead of numbers. To keep things simple, she works only with polynomials whose coefficients are 0ドル$ or 1ドル,ドル that is, each power of $x$ appears at most once.

The game works like this:

• If the polynomial has a constant term (a term that does not depend on $x$), Aline multiplies the polynomial by $(x + 1)$ and then adds 1ドル$. If any resulting coefficient equals 2ドル,ドル the corresponding term is discarded (note that coefficients greater than 2ドル$ cannot arise).
• If the polynomial has no constant term, Aline divides the polynomial by $x$.

This process is repeated until the polynomial reduces to $P(x) = 1$.

Consider $P(x) = x^3 + 1$. In the first step there is a constant term, so we calculate:

$(x^3 + 1) \cdot (x + 1) + 1 = x^4 + x^3 + x + 1 + 1$.

Since the coefficient of the constant term is 2ドル,ドル this term is discarded, leaving:

$x^4 + x^3 + x$.

Next, since there is no constant term, we divide by $x$:

$x^3 + x^2 + 1$.

Continuing:

• Step 3ドル$: $x^4 + x^2 + x$
• Step 4ドル$: $x^3 + x + 1$
• Step 5ドル$: $x^4 + x^3 + x^2$
• Step 6ドル$: $x^3 + x^2 + x$
• Step 7ドル$: $x^2 + x + 1$
• Step 8ドル$: $x^3$
• Step 9ドル$: $x^2$
• Step 10ドル$: $x$
• Step 11ドル$: 1ドル$

In total, it took 11ドル$ operations to reach the polynomial $P(x) = 1$.

Aline needs help to study this variation of the Collatz Conjecture. Since doing these calculations manually is prone to errors, write a program that determines the number of operations needed until the polynomial becomes $P(x) = 1$.

입력

The first line contains an integer $N$ (0ドル ≤ N ≤ 20$), indicating the degree of the polynomial.

The second line contains $N + 1$ integers $a_N , a_{N−1}, \dots , a_0$ (each equal to 0ドル$ or 1ドル$), where $a_i = 1$ indicates that the term $x^i$ is present in the polynomial, and $a_i = 0$ indicates that it is not. Note that $a_N = 1,ドル since the degree of the polynomial is $N$.

출력

Your program must output a single line, containing an integer, representing the number of operations needed until the polynomial becomes $P(x) = 1$.

제한

노트