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: Runtime Error

Solution code:
/*input
8
657312726 129662684 181537270 324043958 468214806 916875077 825989291 319670097
*/

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <math.h>

using namespace std;

#define pb                push_back
#define pp                pop_back
#define pf                pop_front
#define nl                cout << "\n"
#define MIN(con)          (*min_element(ALL(con))) 
#define MAX(con)          (*max_element(ALL(con)))
#define ALL(cont)         (cont).begin(),(cont).end()
#define NX(cont)          next_permutation(ALL(cont))
#define PX(cont)          prev_permutation(ALL(cont))
#define prec(n)           cout << fixed << setprecision(n)
#define PI                3.14159265358979323846264338327951
#define FH(it,c)          for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++ it)
#define ff                first
#define ss                second
#define all(c)            c.begin(),c.end()
#define fill(a,v)         memset(a,v,sizeof a)
#define rep(i,a,b)        for(ll i=a;i<b;i++)
#define rrep(i,a,b)       for(ll i=a;i>=b;i--)
#define srep(i,s)         for(ll i=0;s[i]!='\0';i++)
#define nn                cout<<"\n"
#define sp                cout<<" "
#define mod               1000000007    //9
#define ifalse            ios_base::sync_with_stdio(false),cin.tie(NULL)

using ll = long long;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<string> vst;
typedef pair<ll,ll> pll;
typedef pair<char,ll> pcl;
typedef pair<string,ll> psl;
typedef set<ll> sll;
typedef set<char> sc;
typedef set<string> sst;
typedef map<char,ll> mcl;
typedef map<ll,ll> mll;
typedef map<string,ll> msl;

using ld = long double;
 
template < typename T > inline T LCM(T a, T b)            { return (a * b) / GCD(a, b); }
template < typename T > inline T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > inline string toString(T a)       {return to_string(a); }  // Convert int to string
template < typename T > inline void toInt(string s, T &x) { stringstream str(s); str >> x;}  // Convert string to int

inline ll add(ll x, ll y) { x += y; if(x >= mod) x -= mod; return x; }
inline ll sub(ll x, ll y) { x -= y; if(x < 0) x += mod; return x; }
inline ll mul(ll x, ll y) { return ((x % mod) * (y % mod)) % mod; }

inline ll powr(ll a, ll b){
    ll x = 1LL;
    while(b) {
        if(b & 1) x = mul(x, a);
        a = mul(a, a);
        b >>= 1;
    }
    return x;
}

inline ll inv(ll a) { return powr(a, mod - 2);}

const int inv2 = (mod + 1) >> 1;
const ll INF =  999999999999999999;
const int inf = 999999999;

bool check(ll n)
{
    if(n == 1) return 0;
    if(n == 2 or n == 3) return 1;
    if(n % 2 == 0 or n % 3 == 0) return 0;

    for(ll i = 5; i * i <= n; i += 6) if(n % i == 0 or n % (i + 2) == 0) return 0;
    return 1;
}


/*********************************************START**************************************************************/

int main()
{
    ifalse;
    int n;
    cin >> n;
    vector < ll > a(n);	
    rep(i,0, n) {
    	cin >> a[i];
    }
    if(n == 1) {
    	return cout << "0", nl, 0;
    } 

    ll cnt = 0;
    if(a[0] > a[1]) {
    	cnt ++;
    	a[0] *= -2;
    }
    for(int i = 2; i < n; i ++) {
    	if(a[i - 1] > a[i]) {
    		if((a[i - 1]  * (-2LL)) >= a[i - 2]) {
    			a[i - 1] *= -2LL;
    			cnt ++;
    		}
    		while(a[i - 1] > a[i]) {
    			a[i] *= 4LL;
    			cnt += 2;
    			if(a[i] < 0) {
    				cout << "-1";
    				return 0;
    			}
    		}
    	}
    }
    cout << cnt, nl;
    return 0;
}

Submission status: Runtime Error

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:
         if a[i+1] * -2 > 10 **9:
            count = -1
            break
        else:
            a[i+1] = a[i+1] * -2
            count += 1

print(count)
# except EOFError:
#     pass

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define int long long   // aaaaaaaaaaaaaaaaaa
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define SIZE(buff) (sizeof(buff)/sizeof(buff[0]))
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
template<typename T, typename U>ostream& operator << (ostream& os, pair<T, U>& pair_var)
{os << "(" << pair_var.first << ", " << pair_var.second << ")";return os;}
// head

int t,q,m,n,k,res,tmp,tmp2;
int a[200010] = {};
int b[200010] = {};
//vector<PII> g[500010];
queue<int> que2;
int dp[200010][18]={};
int dp2[200010][18]={};
//string s;

signed main() {
	cin.tie(0);
    ios::sync_with_stdio(false);
	std::cin >>n;
	rep(i,0,n) {
		cin>> a[i];
		b[i] = a[i]*(-2);
	}
	rep(i,0,16) dp[n][i] = i;
	per(i,1,n){
		rep(j,0,16){
			tmp = 1LL<<60;
			rep(x,0,16){
				tmp2 = 0;
				k = a[i];
				while(a[i-1] > k){
					k*=4;
					tmp2 += 1;
				}
				k = a[i-1];
				while(a[i] > k){
					k*= 4;
					tmp2-=1;
				}
				tmp = min(tmp,dp[i+1][x]+max(0LL,tmp2+j-x)*(n-i)+j);
			}
			dp[i][j] = tmp;
		}
	}
	rep(i,0,16) dp2[1][i] = i;
	rep(i,2,n+1){
		rep(j,0,16){
			tmp = 1LL<<60;
			rep(x,0,16){
				tmp2 = 0;
				k = b[i-2];
				while(b[i-1] < k){
					k*=4;
					tmp2 += 1;
				}
				k = b[i-1];
				while(b[i-2] < k){
					k*=4;
					tmp2 -= 1;
				}
				tmp = min(tmp,dp2[i-1][x]+max(0LL,tmp2+j-x)*(i-1)+j);
			}
			dp2[i][j] = tmp;
		}
	}
	res = 1LL<<60;
	rep(i,1,n+1){
		res = min(res,dp[i][0]*2+dp2[i-1][0]*2+i-1);
	}
    cout<<res<<endl;
}

Submission status: Runtime Error

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
        else:
            b = a >> cur
            if pa >= b:
                cur = ceil(log(pa / b, 4)) * 2
                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: Runtime Error

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
        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: Runtime Error

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: Runtime Error

Solution code:
n,x=map(int,input().split())
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: Runtime Error

Solution code:
import collections
import math


def main():
    n = int(input())
    a = list(map(int, input().split()))

    lft = 0
    rgt = n
    while rgt - lft > 2:
        mi1 = (lft * 2 + rgt) // 3
        mi2 = (lft + rgt * 2) // 3
        ret1 = eval(a, mi1)
        ret2 = eval(a, mi2)
        if ret1 < ret2:
            rgt = mi2
        else:
            lft = mi1

    hoge = [eval(a, i) for i in range(lft, min([lft + 3, n]))]
    # hoge = [eval(a, i) for i in range(n)]
    print(min(hoge) if hoge else eval(a, n - 1))


def eval(a, m):
    ret = m
    if m > 0:
        tmp = a[m - 1]
        for i in range(m - 1, 0, -1):
            if a[i - 1] < tmp:
                cnt = math.ceil(math.log(tmp / a[i - 1], 4))
                if cnt < 0:
                    return -1
                ret += cnt * 2
                tmp = a[i - 1] * 4 ** cnt
            else:
                tmp = a[i - 1]
    tmp = a[m]
    for i in range(m + 1, len(a)):
        if a[i] < tmp:
            cnt = math.ceil(math.log(tmp / a[i], 4))
            if cnt < -1:
                return -1
            ret += cnt * 2
            tmp = a[i] * 4 ** cnt
        else:
            tmp = a[i]

    return ret


main()

Submission status: Runtime Error

Solution code:
import collections
import math


def main():
    n = int(input())
    a = list(map(int, input().split()))

    lft = 0
    rgt = n
    while rgt - lft > 2:
        mi1 = (lft * 2 + rgt) // 3
        mi2 = (lft + rgt * 2) // 3
        ret1 = eval(a, mi1)
        ret2 = eval(a, mi2)
        if ret1 < ret2:
            rgt = mi2
        else:
            lft = mi1

    hoge = [eval(a, i) for i in range(lft, min([lft + 3, n]))]
    # hoge = [eval(a, i) for i in range(n)]
    print(min(hoge) if hoge else eval(a, n - 1))


def eval(a, m):
    ret = m
    if m > 0:
        tmp = a[m - 1]
        for i in range(m - 1, 0, -1):
            if a[i - 1] < tmp:
                cnt = math.ceil(math.log(tmp / a[i - 1], 4))
                if cnt < 0:
                    return -1
                ret += cnt * 2
                tmp = a[i - 1] * 4 ** cnt
            else:
                tmp = a[i - 1]
    tmp = a[m]
    for i in range(m + 1, len(a)):
        if a[i] < tmp:
            cnt = math.ceil(math.log(tmp / a[i], 4))
            if cnt < -1
                return -1
            ret += cnt * 2
            tmp = a[i] * 4 ** cnt
        else:
            tmp = a[i]

    return ret


main()

Submission status: Runtime Error

Solution code:
import collections
import math


def main():
    n = int(input())
    a = list(map(int, input().split()))

    lft = 0
    rgt = n
    # while rgt - lft > 2:
    #     mi1 = (lft * 2 + rgt) // 3
    #     mi2 = (lft + rgt * 2) // 3
    #     ret1 = eval(a, mi1)
    #     ret2 = eval(a, mi2)
    #     if ret1 < ret2:
    #         rgt = mi2
    #     else:
    #         lft = mi1

    # hoge = [eval(a, i) for i in range(lft, min([lft + 3, n]))]
    hoge = [eval(a, i) for i in range(n)]
    print(min(hoge) if hoge else eval(a, n - 1))


def eval(a, m):
    ret = m
    if m > 0:
        tmp = a[m - 1]
        for i in range(m - 1, 0, -1):
            if a[i - 1] < tmp:
                cnt = math.ceil(math.log(tmp / a[i - 1], 4))
                ret += cnt * 2
                tmp = a[i - 1] * 4 ** cnt
            else:
                tmp = a[i - 1]
    tmp = a[m]
    for i in range(m + 1, len(a)):
        if a[i] < tmp:
            cnt = math.ceil(math.log(tmp / a[i], 4))
            ret += cnt * 2
            tmp = a[i] * 4 ** cnt
        else:
            tmp = a[i]

    return ret


main()

Submission status: Runtime Error

Solution code:
import collections
import math


def main():
    n = int(input())
    a = list(map(int, input().split()))

    lft = 0
    rgt = n + 1
    while rgt - lft > 2:
        mi1 = (lft * 2 + rgt) // 3
        mi2 = (lft + rgt * 2) // 3
        ret1 = eval(a, mi1)
        ret2 = eval(a, mi2)
        if ret1 < ret2:
            rgt = mi2
        else:
            lft = mi1

    hoge = [eval(a, i) for i in range(lft, min([lft + 3, n]))]
    print(min(hoge) if hoge else eval(a, n-1) )


def eval(a, m):
    ret = m
    if m > 0:
        tmp = a[m - 1]
        for i in range(m - 1, 0, -1):
            if a[i - 1] < tmp:
                cnt = math.ceil(math.log(tmp / a[i - 1], 4))
                ret += cnt * 2
                tmp = a[i - 1] * 4 ** cnt
            else:
                tmp = a[i - 1]
    tmp = a[m]
    for i in range(m + 1, len(a)):
        if a[i] < tmp:
            cnt = math.ceil(math.log(tmp / a[i], 4))
            ret += cnt * 2
            tmp = a[i] * 4 ** cnt
        else:
            tmp = a[i]

    return ret


main()

Submission status: Runtime Error

Solution code:
N = int( input())
A = [ int( input()) for _ in range(N)]
A.sort()
T = A[-1] - A[0]
if N == 1:
    if A[0]%2 == 0:
        ans = "second"
    else:
        ans = "first"
elif T > 0:
    if A[0]%2 == 0:
        ans = "second"
    else:
        ans = "first"
else:
    if (A[0]+N)%2 == 0:
        ans = "second"
    else:
        ans = "first"
print(ans)

Submission status: Runtime Error

Solution code:
import collections
import math


def main():
    n = int(input())
    a = list(map(int, input().split()))
    ret = int(1e18)

    lft = 0
    rgt = n
    while rgt - lft > 2:
        mi1 = (lft * 2 + rgt) // 3
        mi2 = (lft + rgt * 2) // 3
        ret1 = eval(a, mi1)
        ret2 = eval(a, mi2)
        if ret1 < ret2:
            rgt = mi2
        else:
            lft = mi1

    print(min([eval(a, i) for i in range(lft, min([lft + 3, n]))]))

def eval(a, m):
    ret = m
    if m > 0:
        tmp = a[m-1]
        for i in range(m-1, 0, -1):
            if a[i-1] < tmp:
                cnt = math.ceil(math.log(tmp / a[i-1], 4))
                ret += cnt * 2
                tmp = a[i-1] * 4**cnt
            else:
                tmp = a[i-1]
    tmp = a[m]
    for i in range(m+1, len(a)):
        if a[i] < tmp:
            cnt = math.ceil(math.log(tmp/a[i], 4))
            ret += cnt * 2
            tmp = a[i] * 4**cnt
        else:
            tmp = a[i]

    return ret


main()

Submission status: Runtime Error

Solution code:
import collections
import math


def main():
    n = int(input())
    a = list(map(int, input().split()))
    ret = int(1e18)

    lft = 0
    rgt = n
    while rgt - lft > 2:
        mi1 = (lft * 2 + rgt) // 3
        mi2 = (lft + rgt * 2) // 3
        ret1 = eval(a, mi1)
        ret2 = eval(a, mi2)
        if ret1 < ret2:
            rgt = mi2
        else:
            lft = mi1

    print(min([eval(a, lft), eval(a, lft+1), eval(a, lft + 2)]))

def eval(a, m):
    ret = m
    if m > 0:
        tmp = a[m-1]
        for i in range(m-1, 0, -1):
            if a[i-1] < tmp:
                cnt = math.ceil(math.log(tmp / a[i-1], 4))
                ret += cnt * 2
                tmp = a[i-1] * 4**cnt
            else:
                tmp = a[i-1]
    tmp = a[m]
    for i in range(m+1, len(a)):
        if a[i] < tmp:
            cnt = math.ceil(math.log(tmp/a[i], 4))
            ret += cnt * 2
            tmp = a[i] * 4**cnt
        else:
            tmp = a[i]

    return ret


main()

Submission status: Runtime Error

Solution code:
import math
def nibun(func, min_, max_):
    left = min_
    right = max_
    while not (left == right):
        mid = (left + right) // 2
        tmp = func(mid)
        if tmp:
            right = mid
        else:
            left = mid + 1
    return left

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

def solve(i=0):
    # i番目以前は-2倍
    ans = i
    last_val = A[i]
    ans += solve_a(A[i],A[i+1:])
    if i>=2:
        ans += solve_a(A[i-1],reversed(A[:i-2]))
    return ans

def solve_a(start_val,A_list):
    tmp_ans = 0
    last_val = start_val
    for index, x in enumerate(A_list):
        # n = 0
        # while x * (4 ** n) < last_val:
        #     n += 1
        # log x + n log 4 < log last_val
        # n < log last_val/x / log 4
        n=0
        if x < last_val:
            n  = math.ceil(math.log(last_val/x,4))
            tmp_ans += 2 * n
        last_val = x * (4** n)
    return tmp_ans
def f(x):
    return solve(x+1) > solve(x)
print(solve(nibun(f,0,N-1)))