Problem:


Score : 800 points

Problem Statement

There are N positive integers A_1, A_2, ..., A_N.
Takahashi can perform the following operation on these integers any number of times:

Choose 1 \leq i \leq N and multiply the value of A_i by -2.

Notice that he multiplies it by minus two.

He would like to make A_1 \leq A_2 \leq ... \leq A_N holds.
Find the minimum number of operations required. If it is impossible, print -1.

Constraints

1 \leq N \leq 200000

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the answer.

Sample Input 1

4
3 1 4 1

Sample Output 1

3

One possible solution is:

Choose i=4 and multiply the value of A_4 by -2. A_1, A_2, A_3, A_4 are now 3, 1, 4, -2.

Choose i=1 and multiply the value of A_1 by -2. A_1, A_2, A_3, A_4 are now -6, 1, 4, -2.

Choose i=4 and multiply the value of A_4 by -2. A_1, A_2, A_3, A_4 are now -6, 1, 4, 4.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

0

A_1 \leq A_2 \leq ... \leq A_N holds before any operation is performed.

Sample Input 3

8
657312726 129662684 181537270 324043958 468214806 916875077 825989291 319670097

Sample Output 3

7



Sample input:
4
3 1 4 1


Sample output:
3

Submission status: Wrong Answer

Solution code:
if __name__=="__main__":
    n = int(input())
    A = [int(i) for i in input().split(' ')]
    ansl = [0 for i in range(n)]
    ansr = [0 for i in range(n)]
    suml = 0
    sumr = 0
    xl = 0
    xr = 0
    for i in range(n):
        l = i
        r = n - i - 1
        if i == 0:
            xl = A[l] * -2
            ansl[l] = 1
            suml = 1

            xr = A[r]
            ansr[r] = 0
            sumr = 0
        else:
            x = A[l] * -2
            ansl[l] = suml + 1
            while xl > x:
                xl *= 4
                ansl[l] += 2
            xl = x
            suml = ansl[l]

            ansr[r] = sumr
            while xr < A[r]:
                xr *= 4
                ansr[r] += 2 * (n - r - 1)
            sumr = ansr[r]
            xr = A[r]
    ans = int(1e18)
    for i in range(n + 1):
        if i == 0:
            ans = min(ans, ansr[i])
        elif i == n:
            ans = min(ans, ansl[i - 1])
        else:
            ans = min(ans, ansl[i - 1] + ansr[i])
        if ans == 5:
            print(i)
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

# [0,border)が負になり、[border,n)が正になるときの操作の回数
def multi_times(border):
    ans = 0
    num = 1
    for i in range(border, n):
        if num <= a[i]:
            num = a[i]
        else:
            tmp = -((-num)//a[i])
            cnt = -(-((tmp-1).bit_length()) // 2)
            num = (4**cnt) * a[i]
            ans += cnt * 2

    num = 1
    for i in range(0, border)[::-1]:
        ans += 1
        if num <= a[i]:
            num = a[i]
        else:
            tmp = -((-num)//a[i])
            cnt = -(-((tmp-1).bit_length()) // 2)
            num = (4**cnt) * a[i]
            ans += cnt * 2
    return ans


ok = n+1
ng = 0
 
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if mid == 0 or mid == n:
        print(multi_times(mid))
        exit()
    l = multi_times(mid-1)
    m = multi_times(mid)
    r = multi_times(mid+1)
    if l <= m <= r:
        ok = mid
    elif l >= m >= r:
        ng = mid
    else:
        print(min(l,m,r))
        exit()
mid = (ok+ng)//2
print(min(multi_times(mid),multi_times(max(0, mid-1)),multi_times(min(n, mid+1))))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

# [0,border)が負になり、[border,n)が正になるときの操作の回数
def multi_times(border):
    ans = 0
    num = 1
    for i in range(border, n):
        if num <= a[i]:
            num = a[i]
        else:
            tmp = -((-num)//a[i])
            cnt = -((-tmp.bit_length())//2)
            num = (4**cnt) * cnt * a[i]
            ans += cnt * 2

    num = 1
    for i in range(0, border)[::-1]:
        ans += 1
        if num <= a[i]:
            num = a[i]
        else:
            tmp = -((-num)//a[i])
            cnt = -((-tmp.bit_length())//2)
            num = (4**cnt) * a[i]
            ans += cnt * 2
    return ans
s = float("inf")
for i in range(n+1):
    s = min(s, multi_times(i))
print(s)

Submission status: Wrong Answer

Solution code:
try:
    n = int(input())
    a = list(map(int, input().split()))
    i = 0
    count = 0
    while (i < n - 1):
        if a[i] <= a[i+1]:
            i += 1
        elif i == 0:
            a[i] = a[i] * -2
            count += 1
        else:
            a[i+1] = a[i+1] * -2
            count += 1

    print(count)
except EOFError:
    pass

Submission status: Wrong Answer

Solution code:
try:
    n = int(input())
    a = list(map(int, input().split()))
#    print(a)
    i = 0
    count = 0
    while (i < n - 1):
        if a[i] <= a[i+1]:
            i += 1
        elif i == 0:
            a[i] = a[i] * -2
#            print(a)
            count += 1
        else:
            # print(a[i+1] * -2, 10 **9)
            # print(a[i+1] * -2 > 10 **9)
            if a[i+1] * -2 > 10 **9:
                count = -1
                break
            else:
                a[i+1] = a[i+1] * -2
#                print(a)
                count += 1

    print(count)
except EOFError:
    pass

Submission status: Wrong Answer

Solution code:
from math import ceil,log
N=int(input())
A=[int(i) for i in input().split()]
def f(A):
    dp=[0]*16
    L=[0]*N
    for i in range(16):
        dp[i]=i
    for n in range(N-2,-1,-1):
        ndp=[0]*16
        nx=ceil(log(A[n]/A[n+1])/log(4)) #A
        for x in range(16):
            dx=nx+x
            if dx <=15:
                #print(max(0,dx))
                ndp[x]=dp[max(0,dx)]+x
            else:
                ndp[x]=dp[15]+x+(N-1-n)*(dx-15)
        dp=ndp
        L[n]=dp[0]
    return L

K=f(A)+[0]
L=[0]+f(A[::-1])[::-1]
ans=10**9
for i in range(N+1):
    ans=min(ans,i+2*L[i]+2*K[i])
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil,log
N=int(input())
A=[int(i) for i in input().split()]
def f(A):
    dp=[0]*16
    L=[0]*N
    for i in range(16):
        dp[i]=i
    for n in range(N-2,-1,-1):
        ndp=[0]*16
        nx=ceil(log(A[n]/A[n+1])/log(4)) #A
        for x in range(16):
            dx=nx+x
            if dx <=15:
                #print(max(0,dx))
                ndp[x]=dp[max(0,dx)]+x
            else:
                ndp[x]=dp[15]+x+(N-1-n)*(dx-15)
        dp=ndp
        L[n]=dp[0]
    return L

K=f(A)+[0]
L=[0]+f(A[::-1])[::-1]
ans=10**9
for i in range(N):
    ans=min(ans,i+2*L[i]+2*K[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A =  [int(i) for i in input().split()]

dp = [0]*(N + 1)

for i in range(N-1):
    if A[N-2-i] > A[N-1-i]:
        aa = math.ceil(math.log(A[N-2-i]/A[N-1-i], 4))
        dp[i+2] = dp[i+1] + aa * (i + 1)
    else:
        dp[i+2] = dp[i+1]

dp2 = [0]*(N + 1)

for i in range(N-1):
    if A[i] < A[i+1]:
        aa = math.ceil(math.log(A[i+1]/A[i], 4))
        dp2[i+2] = dp2[i+1] + aa * (i + 1)
    else:
        dp2[i+2] = dp2[i+1]


res = [dp[N-i] * 2 + dp2[i] * 2 + i for i in range(N+1)]

print(min(res))

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int,input().split(' ')))

m = [-1]*N
p = [-1]*N

m[N-1]=0
for i in range(N-2,-1,-1):
	if a[i]<=a[i+1]:
		m[i] = m[i+1]
	else:
		k=int(-(-(a[i]/a[i+1])//4))
		m[i] = m[i+1] + 2*k*(N-1-i)

p[0] = 0
for i in range(1,N):
	if a[i-1]>=a[i]:
		p[i] = p[i-1]
	else:
		k=int(-(-(a[i]/a[i-1])//4))
		p[i] = p[i-1] + 2*k*i

cnt = [m[i]+p[i]+i for i in range(N)]
print(min(cnt))

Submission status: Wrong Answer

Solution code:
import math

N=input()
A=map(int,raw_input().split())

DP=[]

A_gap=[]
A_gap_r=[0]
for i in range(N-1):
    if A[i]>=A[i+1]:
        A_gap.append(int(math.ceil(math.log(float(A[i])/A[i+1],4))))
        A_gap_r.append(0)
    else:
        A_gap.append(0)
        A_gap_r.append(int(math.ceil(math.log(float(A[i+1])/A[i],4))))

DP.append(sum(2*A_gap[i]*(N-i-1) for i in range(len(A_gap))))
for i in range(N-1):
    DP.append(DP[-1]+1+2*A_gap_r[i]*i-2*A_gap[i]*(N-i-1))
    if i>min(DP):
        break
print min(DP)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
c=0
a=0
index=0
buf=[-1 for i in range(N)]
for i in range(N-1):
    if A[i+1]<A[i] and a==0:
        buf[i]=i
    elif A[i+1]>=A[i] and index==0:
        a=1
        index=i+1
    elif A[i+1]>=A[index] and index!=0:
        index=i+1
    elif A[index]>A[i+1] and index!=0:
        buf[i+1]=i+1
if len(buf)>0:
    if buf[0]==0:
        i=0
        while buf[i]!=-1:
            A[buf[i]]=-2*A[buf[i]]
            i+=1
            c+=1
    for x in buf:
            if x!=-1 and x!=0:
                while A[x-1]>A[x]:
                    A[x]=4*A[x]
                    c+=2
print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0

for i in range(n//2):
 if a[i]<=a[i+1]:
  continue
 while a[i]<=a[i+1]:
  a[i]*=-2
  ans+=1
  if a[i]>0 :
   a[i]=a[i]*-2
   ans+=1
  
for i in range(n-1):
 if i<n//2:
  continue
 if a[i]<=a[i+1]:
  continue
 while a[i]<=a[i+1]:
  a[i+1]*=2;
  ans+=1
  if a[i+1]>0:
   a[i+1]*=2;
   ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
F=[0]*(N-1)
G=[0]*(N-1)
H=[0]*(N-1)
I=[0]*(N-1)
t=0
for i in range(N-1):
    for k in range(16):
        if A[i]<=A[i+1]*(4**k):
            H[i]=2*k
            t+=2*k
            break
    F[i]=t
t=0
for i in range(N-2,-1,-1):
    for k in range(16):
        if A[i]*(4**k)>=A[i+1]:
            I[i]=2*k
            t+=2*k
            break
    G[i]=t
Fsum=[0]*N
Gsum=[0]*N
Hsum=[0]*N
Isum=[0]*N
for i in range(N-1):
    Fsum[i+1]=Fsum[i]+F[i]
    Hsum[i+1]=Hsum[i]+H[i]
    Isum[i+1]=Isum[i]+I[i]
for i in range(N-2,-1,-1):
    Gsum[i]=Gsum[i+1]+G[i]
ans=sum(F)
#print(ans)
for i in range(N-1):
    t=i+1
    s=-i*(Isum[N-1]-Isum[i])+Gsum[0]-Gsum[i]
    u=-(N-2-i)*(Hsum[i+1]-Hsum[0])+Fsum[N-1]-Fsum[i+1]
    #print(t+s+u,t,s,u)
    ans=min(ans,t+s+u)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def f(a):
    n = len(a)
    l = [0] * (n + 1)
    st = [(0, 0, 0, 1)]
    pu = st.append
    po = st.pop
    for i in xrange(1, n):
        ad = 0
        r = i
        u = 0
        k = 1
        while st:
            v = min(u, st[-1][2])
            y = a[r] << (u - v)
            x = a[st[-1][0]] << (st[-1][2] - v)
            if x >= y:
                break
            _, r, u, q = po()
            c = 0
            while x < y:
                x *= 4
                c += 2
            ad += c * q
            k += q
            u += c
        pu((i, r, u, k))
        l[i+1] = l[i] + ad
    return l

def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, n))
    l = f(a)
    r = f(a[::-1])[::-1]
    ans = 1001001001
    for i in xrange(n + 1):
        if ans > l[i] + i + r[i]:
            ans = l[i] + i + r[i]
    print ans
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def f(a):
    n = len(a)
    l = [0] * (n + 1)
    st = [(a[0], a[0], 1)]
    pu = st.append
    po = st.pop
    for i in xrange(1, n):
        ad = 0
        y = a[i]
        k = 1
        while st and y > st[-1][0]:
            x, z, q = po()
            c = 0
            while x < y:
                x *= 4
                c += 2
            ad += c * q
            k += q
            y = z << c
        pu((a[i], y, k))
        l[i+1] = l[i] + ad
    return l

def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, n))
    l = f(a)
    r = f(a[::-1])[::-1]
    ans = 1001001001
    for i in xrange(n + 1):
        if ans > l[i] + i + r[i]:
            ans = l[i] + i + r[i]
    print ans
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def f(a):
    n = len(a)
    l = [0] * (n + 1)
    st = [(a[0], a[0], 1)]
    pu = st.append
    for i in xrange(1, n):
        ad = 0
        pu((a[i], a[i], 1))
        while len(st) > 1 and st[-1][1] > st[-2][0]:
            z = st[-2][0]
            c = 0
            while z < st[-1][1]:
                z *= 4
                c += 2
            ad += c * st[-2][2]
            b = (a[i], st[-2][1] << c, st[-2][2] + st[-1][2])
            del st[-2:]
            pu(b)
        l[i+1] = l[i] + ad
    return l

def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, n))
    l = f(a)
    r = f(a[::-1])[::-1]
    ans = 1001001001
    for i in xrange(n + 1):
        if ans > l[i] + i + r[i]:
            ans = l[i] + i + r[i]
    print ans
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def f(a):
    n = len(a)
    l = [0] * (n + 1)
    st = [(a[0], a[0], 1)]
    pu = st.append
    for i in xrange(1, n):
        ad = 0
        pu((a[i], a[i], 1))
        while len(st) > 1 and st[-1][1] * 4 > st[-2][0]:
            z = st[-2][0]
            c = 0
            while z < st[-1][1]:
                z *= 4
                c += 2
            ad += c * st[-2][2]
            b = (a[i], st[-2][1] << c, st[-2][2] + st[-1][2])
            del st[-2:]
            pu(b)
        l[i+1] = l[i] + ad
    return l

def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, n))
    l = f(a)
    r = f(a[::-1])[::-1]
    ans = 1001001001
    for i in xrange(n + 1):
        if ans > l[i] + i + r[i]:
            ans = l[i] + i + r[i]
    print ans
main()

Submission status: Wrong Answer

Solution code:
import itertools, sys
def inpl(): return [int(i) for i in input().split()]

N = int(input())
A = inpl()
if N == 1:
    print(0)
    sys.exit()
if N == 2:
    if A[0] <= A[1]:
        print(0)
    else:
        print(1)
    sys.exit()
    
rig = [0]*N
lef = [1]*N 
for i in range(1,N):
    ctr = 0
    pre = A[i-1]
    nex = A[i] 
    while pre < nex:
        pre *= 4
        ctr += 2
    lef[i] = 1 + lef[i-1] + i* ctr 
lef = [0] + lef
rig[N-1] = 0
for i in range(N-1,0,-1):
    ctr = 0
    pre = A[i]
    nex = A[i-1] 
    while pre < nex:
        pre *= 4
        ctr += 2
    rig[i-1] = rig[i] + ctr*(N-i)
print(min([a + b for a, b in zip(lef, rig)]))

Submission status: Wrong Answer

Solution code:

def main():
    buf = input()
    N = int(buf)
    buf = input()
    buflist = buf.split()
    A = list(reversed(list(map(int, buflist))))
    A_inv = list(map(lambda x: x * (-2), A))
    dp_pos = []
    dp_neg = []
    for i in range(N):
        dp_pos.append([])
        dp_neg.append([])
        for j in range(16): # 10**9 < 4**15
            dp_pos[i].append(0)
            dp_neg[i].append(0)
    for j in range(16):
        dp_pos[0][j] = j * 2
        dp_neg[0][j] = j * 2 + 1
    for i in range(1, N):
        # update dp_pos
        count = 0
        factor = 1
        while A[i-1] * factor < A[i]:
            count += 1
            factor *= 4
        dp_pos[i][0] = dp_pos[i-1][count]
        for j in range(1, 16):
            if A[i] * int(4 ** j) <= A[i-1]:
                dp_pos[i][j] = dp_pos[i][j-1] + 2
            else:
                dp_pos[i][j] = dp_pos[i][j-1] + 2 + 2 * i
        # update dp_neg
        count = 0
        factor = 1
        while A_inv[i-1] * factor > A_inv[i]:
            count += 1
            factor *= 4
        dp_neg[i][0] = dp_neg[i-1][count] + 1
        for j in range(1, 16):
            if A_inv[i] * int(4 ** j) >= A_inv[i-1]:
                dp_neg[i][j] = dp_neg[i][j-1] + 2
            else:
                dp_neg[i][j] = dp_neg[i][j-1] + 2 + 2 * i
    #print("dp_pos:")
    #for i in dp_pos:
    #    print(i)
    #print("dp_neg:")
    #for i in dp_neg:
    #    print(i)
    minimum = min(dp_pos[N-1][0], dp_neg[N-1][0])
    for i in range(N-1):
        #print(i, dp_pos[i][0] + dp_neg[N-2-i][0])
        if dp_pos[i][0] + dp_neg[N-2-i][0] < minimum:
            minimum = dp_pos[i][0] + dp_neg[N-2-i][0]
    print(minimum)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def main():
    buf = input()
    N = int(buf)
    buf = input()
    buflist = buf.split()
    A = list(reversed(list(map(int, buflist))))
    A_inv = list(map(lambda x: x * (-2), A))
    dp_pos = []
    dp_neg = []
    for i in range(N):
        dp_pos.append([])
        dp_neg.append([])
        for j in range(16): # 10**9 < 4**15
            dp_pos[i].append(None)
            dp_neg[i].append(None)
    for j in range(16):
        dp_pos[0][j] = j * 2
        dp_neg[0][j] = j * 2 + 1
    for i in range(1, N):
        # update dp_pos
        count = 0
        factor = 1
        while A[i-1] * factor < A[i]:
            count += 1
            factor *= 4
        dp_pos[i][0] = dp_pos[i-1][count]
        for j in range(1, 16):
            if A[i] * int(4 ** j) <= A[i-1]:
                dp_pos[i][j] = dp_pos[i][j-1] + 2
            else:
                dp_pos[i][j] = dp_pos[i][j-1] + 2 + 2 * i
        # update dp_neg
        count = 0
        factor = 1
        while A_inv[i-1] * factor > A_inv[i]:
            count += 1
            factor *= 4
        dp_neg[i][0] = dp_neg[i-1][count] + 1
        for j in range(1, 16):
            if A_inv[i] * int(4 ** j) >= A_inv[i-1]:
                dp_neg[i][j] = dp_neg[i][j-1] + 2
            else:
                dp_neg[i][j] = dp_neg[i][j-1] + 2 + 2 * i
    #print("dp_pos:")
    #for i in dp_pos:
    #    print(i)
    #print("dp_neg:")
    #for i in dp_neg:
    #    print(i)
    minimum = min(dp_pos[N-1][0], dp_neg[N-1][0])
    for i in range(N-1):
        #print(i, dp_pos[i][0] + dp_neg[N-2-i][0])
        if dp_pos[i][0] + dp_neg[N-2-i][0] < minimum:
            minimum = dp_pos[i][0] + dp_neg[N-2-i][0]
    print(minimum)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def main():
    buf = input()
    N = int(buf)
    buf = input()
    buflist = buf.split()
    A = list(reversed(list(map(int, buflist))))
    A_inv = list(map(lambda x: x * (-2), A))
    dp_pos = []
    dp_neg = []
    for i in range(N):
        dp_pos.append(None)
        dp_neg.append(None)
    dp_pos[0] = 0
    dp_neg[0] = 1
    for i in range(1, N):
        # update dp_pos
        dp_pos[i] = dp_pos[i-1]
        count = 0
        factor = 1
        while A[i-1] * factor < A[i]:
            count += 2
            factor *= 4
        dp_pos[i] += count * i
        # update dp_neg
        dp_neg[i] = dp_neg[i-1]
        count = 0
        factor = 1
        while A_inv[i-1] * factor > A_inv[i]:
            count += 2
            factor *= 4
        dp_neg[i] += count * i + 1
    #print(dp_pos)
    #print(dp_neg)
    minimum = min(dp_pos[N-1], dp_neg[N-1])
    for i in range(N-1):
        #print(i, dp_pos[i] + dp_neg[N-2-i])
        if dp_pos[i] + dp_neg[N-2-i] < minimum:
            minimum = dp_pos[i] + dp_neg[N-2-i]
    print(minimum)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import log, ceil


def _check(ascends):
    ret = 0
    cur = 0
    for asc in ascends:
        cur = max(0, cur + asc)
        ret += cur
    return ret


def check(x, ascends, descends):
    ret = x
    ret += _check(ascends[x:])
    ret += _check(descends[n - x:])
    return ret


def prepare(aaa):
    ascends = [ceil(log(a1 / a2, 4)) * 2 for a1, a2 in zip(aaa, aaa[1:])]
    descends = [ceil(log(a1 / a2, 4)) * 2 for a1, a2 in zip(reversed(aaa), reversed(aaa[:-1]))]
    return ascends, descends


def solve(n, aaa):
    if n > 10000:
        return False
    ascends, descends = prepare(aaa)
    # print(ascends, descends)
    ans = float('inf')
    for i in range(n + 1):
        ans = min(ans, check(i, ascends, descends))
    return ans


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
from math import log, ceil


def _check(ascends):
    ret = 0
    cur = 0
    for asc in ascends:
        cur = max(0, cur + asc)
        ret += cur
    return ret


def check(x, ascends, descends):
    ret = x
    ret += _check(ascends[x:])
    ret += _check(descends[n - x:])
    return ret


def prepare(aaa):
    ascends = [ceil(log(a1 / a2, 4)) * 2 for a1, a2 in zip(aaa, aaa[1:])]
    descends = [ceil(log(a1 / a2, 4)) * 2 for a1, a2 in zip(reversed(aaa[:-1]), reversed(aaa))]
    return ascends, descends


def solve(n, aaa):
    ascends, descends = prepare(aaa)
    # print(ascends, descends)
    ans = float('inf')
    for i in range(n + 1):
        ans = min(ans, check(i, ascends, descends))
    return ans


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
from math import log, ceil


def _check(aaa):
    ret = 0
    cur = 0
    pa = -1
    for a in aaa:
        if pa == a:
            ret += cur
        elif pa >= (a >> cur):
            d = ceil(log(pa / a, 4)) * 2
            cur += d
            ret += cur
            # print(pa, a, d, cur, ret)
        pa = a
    return ret


def check(x, aaa):
    ret = x
    ret += _check(aaa[x:])
    ret += _check(reversed(aaa[:x]))
    return ret


def solve(n, aaa):
    l = 0
    r = n
    while l < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        res1 = check(m1, aaa)
        res2 = check(m2, aaa)
        # print(l, r, m1, m2, res1, res2)
        if res1 > res2:
            l = m2
        else:
            r = m1
    return check(r, aaa)


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

right = [0 for i in range(n)]
left = [0 for i in range(n)]

for i in range(n-1):
    count = 0
    memo = a[i+1]
    while a[i] > a[i+1]:
        a[i+1] *= 4
        count += 2
    a[i+1] = memo
    right[i+1] = count

for i in range(n-1):
    right[i+1] += right[i]

for i in range(n-1):
    right[i+1] += right[i]



for i in range(n-1):
    count = 0
    memo = a[i]
    while a[i+1] > a[i]:
        a[i] *= 4
        count += 2
    a[i] = memo
    left[i] = count

for i in reversed(range(n-1)):
    left[i] += left[i+1]

for i in reversed(range(n-1)):
    left[i] += left[i+1]

ans = float('inf')
for i in range(n+1):
    count = 0
    if i == 0:
        count += right[n-1] - right[i]
        ans = min(ans, count)
    elif i == n:
        count += n
        count += left[0] - left[n-1]
        ans = min(ans, count)
    else:
        count += i
        count += right[n-1] - right[i]
        count += left[0] - left[i-1]
        ans = min(ans, count)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import functools

N = int(input())
A = list(map(int,input().split()))
AR = list(reversed(A))
N_I = [0 for _ in range(N-1)]
N_D = [1 for _ in range(N)]

for i in range(1,N):
    if A[i-1] > A[i]:
        N_I[i-1] += math.ceil(math.log(A[i-1]/A[i],4)) *2*  (N-i)
for i in range(1,N):
    if AR[i-1] > AR[i]:
        N_D[N-i] += math.ceil(math.log(AR[i-1]/AR[i],4)) *2*  (N-i)

# print(N_I)
# print(N_D)

N_I_SUM = []
N_D_SUM = [0]
_sum =0
for x in reversed(N_I):
    _sum +=x
    N_I_SUM.append(_sum)

N_I_SUM.reverse()
N_I_SUM.append(0)
_sum =0
for x in N_D:
    _sum+=x
    N_D_SUM.append(_sum)
#
# print(N_I_SUM)
# print(N_D_SUM)

print(min(N_D_SUM[i]+N_I_SUM[i] for i in range(N)))

Submission status: Wrong Answer

Solution code:
def func(i):
    return numMinuss[i] * numPluss[i]

N = int(input())
As = list(map(int, input().split()))

# numPluss[i]: As[i]以降を、0＜As[i]≦As[i+1]≦…≦As[N-1]にするために必要な操作回数min
numPluss = [0] * (N+1)
stack = [(N, As[-1])]
for i in reversed(range(1, N)):
    if As[i-1] > As[i]:
        k = ((As[i-1] // As[i] - 1).bit_length() + 1) // 2 * 2
        numPluss[i] = k

# numPluss[i]: As[i]以前を、As[0]≦…≦As[i-1]≦As[i]＜0にするために必要な操作回数min
numMinuss = [0] * (N+1)
for i in range(N-1):
    pass

# 正負の区切りを全通り試す
ans = float('inf')
for i in range(N):
    num = func(i)
    ans = min(ans, num)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log, ceil


def _check(aaa):
    ret = 0
    cur = 0
    pa = -1
    for a in aaa:
        if pa < a:
            pass
        elif pa == a:
            ret += cur
        else:
            d = ceil(log(pa / a, 4)) * 2
            cur += d
            ret += cur
            # print(pa, a, d, cur, ret)
        pa = a
    return ret


def check(x, aaa):
    ret = x
    ret += _check(aaa[x:])
    ret += _check(reversed(aaa[:x]))
    return ret


def solve(n, aaa):
    l = 0
    r = n
    while l < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        res1 = check(m1, aaa)
        res2 = check(m2, aaa)
        # print(l, r, m1, m2, res1, res2)
        if res1 > res2:
            l = m2
        else:
            r = m1
    return check(r, aaa)


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
from math import log, ceil


def _check(aaa):
    ret = 0
    cur = 0
    pa = -1
    for a in aaa:
        if pa >= (a >> cur):
            d = ceil(log(pa / a, 4)) * 2
            cur += d
            ret += cur
            # print(pa, a, d, cur, ret)
        pa = a
    return ret


def check(x, aaa):
    ret = x
    ret += _check(aaa[x:])
    ret += _check(reversed(aaa[:x]))
    return ret


def solve(n, aaa):
    l = 0
    r = n
    while l < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        res1 = check(m1, aaa)
        res2 = check(m2, aaa)
        # print(l, r, m1, m2, res1, res2)
        if res1 > res2:
            l = m2
        else:
            r = m1
    return check(r, aaa)


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
import math
import functools

N = int(input())
A = list(map(int,input().split()))
N_I = [0 for _ in range(N-1)]
N_D = [1 for _ in range(N)]

for i in range(1,N):
    if A[i-1] > A[i]:
        N_I[i-1] += math.ceil(math.log(A[i-1]/A[i],4)) *2*  (N-i)
    if A[i-1] < A[i]:
        N_D[i] += math.ceil(math.log(A[i]/A[i-1],4)) *2*i


# print(N_I)
# print(N_D)

N_I_SUM = []
N_D_SUM = [0]
_sum =0
for x in reversed(N_I):
    _sum +=x
    N_I_SUM.append(_sum)

N_I_SUM.reverse()
N_I_SUM.append(0)
_sum =0
for x in N_D:
    _sum+=x
    N_D_SUM.append(_sum)
#
# print(N_I_SUM)
# print(N_D_SUM)

print(min(N_D_SUM[i]+N_I_SUM[i] for i in range(N)))

Submission status: Wrong Answer

Solution code:
from math import log, ceil


def _check(aaa):
    ret = 0
    cur = 0
    pa = -1
    for a in aaa:
        if pa > (a >> cur):
            d = ceil(log(pa / a, 4)) * 2
            cur += d
            ret += cur
            # print(pa, a, d, cur, ret)
        pa = a
    return ret


def check(x, aaa):
    ret = x
    ret += _check(aaa[x:])
    ret += _check(reversed(aaa[:x]))
    return ret


def solve(n, aaa):
    l = 0
    r = n
    while l < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        res1 = check(m1, aaa)
        res2 = check(m2, aaa)
        # print(l, r, m1, m2, res1, res2)
        if res1 > res2:
            l = m2
        else:
            r = m1
    return check(r, aaa)


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
import sys
import copy
import math
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
A=[math.log(A[i],4) for i in range(N)]

#負にする個数で場合分け

MIN=0
MAX=N-1
#何個負にするかで二分探索

while True:
    j=(MAX+MIN)//2
    l=min(j+1,N-1)

    ANSj=j
    AR=copy.copy(A)
    for i in range(j+1,N):
        if AR[i]<AR[i-1]:
            x=math.ceil(AR[i-1]-AR[i])
            AR[i]+=x
            ANSj+=2*x

    for i in range(j-2,-1,-1):
        if AR[i]<AR[i+1]:
            x=math.ceil(AR[i+1]-AR[i])
            AR[i]+=x
            ANSj+=2*x

    #print(j,AR,ANSj)

    ANSl=l
    AR=copy.copy(A)
    for i in range(l+1,N):
        if AR[i]<AR[i-1]:
            x=math.ceil(AR[i-1]-AR[i])
            AR[i]+=x
            ANSl+=2*x

    for i in range(l-2,-1,-1):
        if AR[i]<AR[i+1]:
            x=math.ceil(AR[i+1]-AR[i])
            AR[i]+=x
            ANSl+=2*x

    #print(l,AR,ANSl)

    if MAX-MIN<=1:
        print(min(ANSj,ANSl))
        break

    if ANSj<=ANSl:
        MAX=j
    else:
        MIN=l

Submission status: Wrong Answer

Solution code:
from math import ceil


def _check(aaa):
    ret = 0
    cur = 0
    pa = -1
    for a in aaa:
        if pa > (a >> cur):
            d = ceil(pa / a / 4) * 2
            cur += d
            ret += cur
        pa = a
    return ret


def check(x, aaa):
    ret = x
    ret += _check(aaa[x:])
    ret += _check(reversed(aaa[:x]))
    return ret


def solve(n, aaa):
    l = 0
    r = n
    while l < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        res1 = check(m1, aaa)
        res2 = check(m2, aaa)
        # print(l, r, m1, m2, res1, res2)
        if res1 > res2:
            l = m1 + 1
        else:
            r = m1
    return check(r, aaa)


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
import math
import functools

N = int(input())
A = list(map(int,input().split()))
N_I = [0 for _ in range(N-1)]
N_D = [1 for _ in range(N-1)]

for i in range(1,N):
    if A[i-1] > A[i]:
        N_I[i-1] += math.ceil(math.log(A[i-1]/A[i],4)) *2*  (N-i)
    if A[i-1] < A[i]:
        N_D[i-1] = math.ceil(math.log(A[i]/A[i-1],4)) *2* (i-1)+1


# print(N_I)
# print(N_D)

N_I_SUM = []
N_D_SUM = [0]
_sum =0
for x in reversed(N_I):
    _sum +=x
    N_I_SUM.append(_sum)

N_I_SUM.reverse()
N_I_SUM.append(0)
_sum =0
for x in N_D:
    _sum+=x
    N_D_SUM.append(_sum)
#
# print(N_I_SUM)
# print(N_D_SUM)

print(min(N_D_SUM[i]+N_I_SUM[i] for i in range(N)))