Problem:


Score : 600 points

Problem Statement

Given is an integer sequence of length N+1: A_0, A_1, A_2, \ldots, A_N. Is there a binary tree of depth N such that, for each d = 0, 1, \ldots, N, there are exactly A_d leaves at depth d? If such a tree exists, print the maximum possible number of vertices in such a tree; otherwise, print -1.

Notes

A binary tree is a rooted tree such that each vertex has at most two direct children.

A leaf in a binary tree is a vertex with zero children.

The depth of a vertex v in a binary tree is the distance from the tree's root to v. (The root has the depth of 0.)

The depth of a binary tree is the maximum depth of a vertex in the tree.

Constraints

0 \leq N \leq 10^5

0 \leq A_i \leq 10^{8} (0 \leq i \leq N)

A_N \geq 1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 A_1 A_2 \cdots A_N

Output

Print the answer as an integer.

Sample Input 1

3
0 1 1 2

Sample Output 1

7

Below is the tree with the maximum possible number of vertices. It has seven vertices, so we should print 7.

Sample Input 2

4
0 0 1 0 2

Sample Output 2

10

Sample Input 3

2
0 3 1

Sample Output 3

-1

Sample Input 4

1
1 1

Sample Output 4

-1

Sample Input 5

10
0 0 1 1 2 3 5 8 13 21 34

Sample Output 5

264



Sample input:
3
0 1 1 2


Sample output:
7

Submission status: Wrong Answer

Solution code:

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x


def main():
    from math import ceil
    N = int(input())
    A = list(map(int, input().split()))

    if(N == 0):
        print(A[0])
        exit(0)
    if(A[0] != 0 or A[N] == 0):
        print(-1)
        exit(0)
    # curは作り出せる最大ノード数
    if(N == 1 and A[1] != 2):
        print(-1)
        exit(0)
    cur = 0
    S = [0] * (N + 1)
    for i in range(N, 0, -1):
        cur += A[i]
        S[i - 1] = cur
    # print(S)

    ans, cur = 0, 2
    node = [0] * (N + 1)
    a = [0] * (N + 1)
    node[0] = 2
    for i in range(1, N + 1):
        if(A[i] > cur):
            print(-1)
            exit(0)
        if(A[i] > pow(2, i)):
            print(-1)
            exit(0)
        cur = 2 * (cur - A[i])
        node[i] = cur

        if(node[i] > S[i]): node[i] = S[i]
        a[i] = node[i - 1] + cur
        # print("i={}, cur={}".format(i, cur))
    # print(node)
    # print(a)
    # 最初の頂点
    print(sum(node) + 1)
    '''
  cur = 0
  for i in range(N, 0, -1):
      cur += A[i]
      if(cur >= 2**(i - 1)): cur = 2**(i - 1)
      # if(cur >= 2 * A[i - 1]): cur = 2 * A[i - 1]
      ans += cur
      print(cur, ans)
  print(ans)

  '''


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)

if bottom == 0 or A[0] >= 1:
  print(-1)
  exit()

ret = 1
children = 1
bottom -= A[0]

for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break

#    if children <= 0 and i != N-1:
#      ret = -1
#      break
      
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    low, high = A[N], A[N]
    maxN = [0] * (N + 1)
    lowN = [0] * (N + 1)
    maxN[N] = A[N]
    lowN[N] = A[N]
    Limit = [10 ** 15] * (N + 1)

    for i in reversed(range(N)):
        leaf = A[i]
        Limit[i] = min(Limit[i], high + leaf)
        if i <= 46: Limit[i] = min(pow(2, i), Limit[i])
        low = (low + 1) // 2 + leaf
        high += leaf
        if low > Limit[i]:
            print(-1)
            break
        else: 
            lowN[i] = low
            maxN[i] = min(high, Limit[i])
    else:
        #print(maxN)
        for i in range(N - 1):
            if (maxN[i] - A[i]) * 2 <= maxN[i+1]: maxN[i + 1] = (maxN[i] - A[i]) * 2
        if maxN[N-1] - A[N-1] <= A[N] <= 2 * (maxN[N-1] - A[N-1]): print(sum(maxN))
        else: print(-1)
        #print(maxN)
        #print(lowN)
            
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N == 0: 
    if A[0] == 1:
        print(1)
        exit()
    else:
        print(-1)
        exit()
if A[0] != 0:
    print(-1)
    exit()


leaf = A
not_leaf = [0] * (N + 1)
not_leaf[0] = 1

for i, a in enumerate(A[1:-1], 1):
    not_leaf[i] = not_leaf[i - 1] * 2 - a

for i in reversed(range(1, N + 1)):
    total = not_leaf[i] + leaf[i]
    prev = not_leaf[i - 1]
    if prev > total:
        not_leaf[i - 1] -= prev - total
    if not_leaf[i - 1] < 0:
        print(-1)
        break
else:
    print(sum(leaf) + sum(not_leaf))

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
a_list_r = a_list[::-1]
ruisekiwa = [a_list_r[0]]
for i in range(1,n+1):
  ruisekiwa.append(ruisekiwa[-1] + a_list_r[i])
ruisekiwa = ruisekiwa[::-1]
max_leaf = a_list[-1]
count = 0
check = True
node = 0
for i in range(n):
  if i == 0:
    if  n == 0 :
      if a_list[0] != 1:
        check = False
        break
      else:
        count = 1
        break
    else:
      count = 1
      node = 1
  else:
    cand = 2 * node
    if cand < a_list[i]:
      check = False
      break
    node = min(ruisekiwa[i+1],2*node - a_list[i])
    count += node + a_list[i]
if check == False:
  print(-1)
elif n == 0 and a_list[0] == 1:
  print(1)
elif 2 * node < a_list[-1]:
  print(-1)
else:
  print(count + a_list[-1])

Submission status: Wrong Answer

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

up = [0] * (N+1)
down = [0] * (N+1)
able = [2 ** i for i in range(N+1)]

up[0] = A[-1]
down[0] = 1
for i in range(1, N+1):
    up[i] = up[i-1] + A[-(i+1)]
    down[i] = (down[i-1] - A[i-1])*2

down = down[::-1]
lst = []
for i in range(N+1):
    lst.append(min(up[i], down[i]))
# print(up, down, lst)
flug = False
for i in lst:
    if i <= 0:
        flug = True
if flug:
    print(-1)
else:
    print(sum(lst))

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
if A[0]>=1:
  print(-1)
  sys.exit()
ans=A[N]
left=1
P=[1 for i in range(N+1)]
for i in range(1,N+1):
  point=left*2
  P[i]=point
  if point-A[i]<1:
    print(-1)
    sys.exit()
  left=point-A[i]
root=A[N]
for i in range(N,0,-1):
  root=min(P[i-1],root+A[i-1])
  ans+=root
print(ans)

Submission status: Wrong Answer

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

pm = sum(A)
e = 1
te = 1
if A[0] != 0 or A[N] == 0:
    print(-1)
else:
    for i in A:
        pm -= i
        e = min((e-i) * 2,pm)
        if e < 0:
            break
        te += e
    if e < 0:
        print(-1)
    else:
        print(te)

Submission status: Wrong Answer

Solution code:

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x


def main():
    from math import ceil
    N = int(input())
    A = list(map(int, input().split()))
    if(A[0] != 0 or A[N] == 0):
        print(-1)
        exit(0)
    # curは作り出せる最大ノード数
    if(N == 0):
        print(A[0])
        exit(0)
    if(N == 1 and A[1] != 2):
        print(-1)
        exit(0)
    cur = 0
    S = [0] * (N + 1)
    for i in range(N, 0, -1):
        cur += A[i]
        S[i - 1] = cur
    # print(S)

    ans, cur = 0, 2
    node = [0] * (N + 1)
    a = [0] * (N + 1)
    node[0] = 2
    for i in range(1, N + 1):
        if(A[i] > cur):
            print(-1)
            exit(0)
        if(A[i] > pow(2, i)):
            print(-1)
            exit(0)
        cur = 2 * (cur - A[i])
        node[i] = cur

        if(node[i] > S[i]): node[i] = S[i]
        a[i] = node[i - 1] + cur
        # print("i={}, cur={}".format(i, cur))
    # print(node)
    # print(a)
    # 最初の頂点
    print(sum(node) + 1)
    '''
  cur = 0
  for i in range(N, 0, -1):
      cur += A[i]
      if(cur >= 2**(i - 1)): cur = 2**(i - 1)
      # if(cur >= 2 * A[i - 1]): cur = 2 * A[i - 1]
      ans += cur
      print(cur, ans)
  print(ans)

  '''


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x


def main():
    from math import ceil
    N = int(input())
    A = list(map(int, input().split()))

    if(N == 0):
        print(-1)
        exit(0)
    if(A[0] != 0 or A[N] == 0):
        print(-1)
        exit(0)
    # curは作り出せる最大ノード数
    if(N == 0):
        print(-1)
        exit(0)
    if(N == 1 and A[1] != 2):
        print(-1)
        exit(0)
    cur = 0
    S = [0] * (N + 1)
    for i in range(N, 0, -1):
        cur += A[i]
        S[i - 1] = cur
    # print(S)

    ans, cur = 0, 2
    node = [0] * (N + 1)
    a = [0] * (N + 1)
    node[0] = 2
    for i in range(1, N + 1):
        if(A[i] > cur):
            print(-1)
            exit(0)
        if(A[i] > pow(2, i)):
            print(-1)
            exit(0)
        cur = 2 * (cur - A[i])
        node[i] = cur

        if(node[i] > S[i]): node[i] = S[i]
        a[i] = node[i - 1] + cur
        # print("i={}, cur={}".format(i, cur))
    # print(node)
    # print(a)
    # 最初の頂点
    print(sum(node) + 1)
    '''
  cur = 0
  for i in range(N, 0, -1):
      cur += A[i]
      if(cur >= 2**(i - 1)): cur = 2**(i - 1)
      # if(cur >= 2 * A[i - 1]): cur = 2 * A[i - 1]
      ans += cur
      print(cur, ans)
  print(ans)

  '''


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)

if bottom == 0 or A[0] >= 1:
  print(-1)
  exit()

ret = 1
children = 1
bottom -= A[0]

for i in range(N):
    children = children * 2 - A[i+1]
    if children <= 0 and i != N-1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Wrong Answer

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

# その段で使用する枝の数
branches = dict()
for idx,a in enumerate(A):
  if idx == 0:
    branch = 1-a
  else:
    branch = branch * 2 - a
  if branch <=0:
    print(-1)
    quit()
  branches[idx] = branch

# 後ろから葉と枝の数(nodes)を計算していく
ans =0 
for idx,leaf in enumerate(reversed(A)):
  if idx == 0:
    nodes = leaf
  else:
    if branches[len(A)-idx-1] <nodes//2:
      print(-1)
      break
    nodes = min(
      leaf + nodes,
      leaf + branches[len(A)-idx-1]
    )
  ans += nodes
else:
  print(ans)

Submission status: Wrong Answer

Solution code:

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x


def main():
    from math import ceil
    N = int(input())
    A = list(map(int, input().split()))

    if(N == 0 and A[0] == 0):
        print(1)
        exit(0)
    if(A[0] != 0 or A[N] == 0):
        print(-1)
        exit(0)
    # curは作り出せる最大ノード数
    if(N == 0):
        print(-1)
        exit(0)
    if(N == 1 and A[1] != 2):
        print(-1)
        exit(0)
    cur = 0
    S = [0] * (N + 1)
    for i in range(N, 0, -1):
        cur += A[i]
        S[i - 1] = cur
    # print(S)

    ans, cur = 0, 2
    node = [0] * (N + 1)
    a = [0] * (N + 1)
    node[0] = 2
    for i in range(1, N + 1):
        if(A[i] > cur):
            print(-1)
            exit(0)
        if(A[i] > pow(2, i)):
            print(-1)
            exit(0)
        cur = 2 * (cur - A[i])
        node[i] = cur

        if(node[i] > S[i]): node[i] = S[i]
        a[i] = node[i - 1] + cur
        # print("i={}, cur={}".format(i, cur))
    # print(node)
    # print(a)
    # 最初の頂点
    print(sum(node) + 1)
    '''
  cur = 0
  for i in range(N, 0, -1):
      cur += A[i]
      if(cur >= 2**(i - 1)): cur = 2**(i - 1)
      # if(cur >= 2 * A[i - 1]): cur = 2 * A[i - 1]
      ans += cur
      print(cur, ans)
  print(ans)

  '''


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:


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


if a == 0 and A[0] == 1:
    print(1)
    exit()


ch = [1]
t = 0
for e,i in enumerate(A):
    t+=i
    if t>=2**i:
        print(-1)
        exit()
    t #

cH = [1]
if A[0]>0:
    print(-1)
    exit()
for e,i in enumerate(A[1:]):
    cH.append(cH[-1]*2-i)
    # ch.append((cH[-1]*2)//(2**i))
# print(ch)
# print(cH)

# ch = ch[:-1]
# ch = ch[::-1]
# ch[0]*=2
# print(ch)
cH = cH[:-1]
cH.append(cH[-1]*2)
cH = cH[::-1]
# print(cH)


if 0 in cH:
    print(-1)
    exit()
A = A[::-1]

ans = 0
n = 0
for e,i in enumerate(A[:]):
    # print(n,ch[e],-1)
    if n//2+(n%2!=0)>cH[e]:
        print(-1)
        exit()
    if n  <= cH[e]:
        # print('ans:',ans,'n:',n)
        ans += n+i
        n+=i
    else:
        # print('ans:',ans,'ch:',cH[e],'i:',i)
        ans +=cH[e]+i
        n = cH[e]+i

    # print('ans:',ans,'n:',n)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
Z = A[-1]
A[-1] = 0
flag = 0
B = A[::-1]
if N==0:
    if A[0]!=1:
        print(-1)
    else:
        print(1)
elif A[0]!=0:
    print(-1)
else:
    sita = [0]*(N+1)
    sita[0] = Z
    for i in range(1,N+1):
        X = B[i-1]+sita[i-1]
        if X<=0:
            flag = 1
            break
        if math.log2(X+B[i]) > (N-i):
            sita[i] = 2**(N-1)-B[i]
        else:
            sita[i] = X
    if flag==0:
        ue = [0]*(N+1)
        ue[0] = 1
        for i in range(1,N+1):
            Y = ue[i-1]*2-A[i]
            if Y>=sita[N-i]:
                ue[i] = sita[N-i]
            else:
                ue[i] = Y
            if ue[i]<=0:
                flag = 1
                break
    if flag==1:
        print(-1)
    else:
        print(sum(B)+sum(ue))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = tuple(map(int, input().split(' ')))

nodes = [0] * (N + 1)
nodes[0] = 1 - A[0]

for index, a in enumerate(A[1:], start=1):
    nodes[index] = nodes[index - 1] * 2 - a
    if nodes[index] < 0:
        print(-1)
        break
else:
    fixed_nodes = [0] * (N + 1)
    fixed_nodes[-1] = A[-1]
    for i in reversed(range(N)):
        fixed_nodes[i] = min(nodes[i], fixed_nodes[i + 1]) + A[i]
    if any([n == 0 for n in fixed_nodes]):
        print(-1)
    else:
        s = sum(fixed_nodes)
        if 2 ** N < s:
            print(-1)
        else:
            print(s)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if A[0] == 1:
    print(1)
    exit()

leaf = A
not_leaf = [0] * (N + 1)
not_leaf[0] = 1

for i, a in enumerate(A[1:-1], 1):
    not_leaf[i] = not_leaf[i - 1] * 2 - a

for i in reversed(range(1, N + 1)):
    total = not_leaf[i]
    prev = not_leaf[i - 1]
    if prev > total:
        not_leaf[i - 1] -= prev - total
    if not_leaf[i - 1] < 0:
        print(-1)
        break
else:
    print(sum(leaf) + sum(not_leaf))

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
asc = [0] * (n + 1)
desc = [0] * (n + 1)
asc[0] = 1
desc[-1] = a_list[-1]
sum = 1

if a_list[0] != 0:
    print(-1)
    exit()

for i in range(n):
    asc[i + 1] = (asc[i] -a_list[i]) * 2
    desc[n - 1 - i] = desc[n - i] + a_list[n - 1 - i]

for i in range(1, n + 1):
    num = min(asc[i], desc[i])
    sum += num
    if num < a_list[i]:
        print(-1)
        exit()

print(sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)

if A[0] >= 1:
  print(-1)
  exit()

ret = 1
children = 1

for i in range(N):
    children = children * 2 - A[i+1]
    if children <= 0 and i != N-1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
a_li = list(map(int, input().split()))
sum_li = []
tmp = 0
for a in reversed(a_li):
    tmp += a
    sum_li.append(tmp)

if a_li[0]>0 and n>0:
    print(-1)
else:
    cnt = 1
    node = 1
    for i in range(1, n+1):
        node = min(node*2-a_li[i], sum_li[n-i-1])
        if node < 0:
            print(-1)
            break
        if i!=n:
            cnt += node + a_li[i]
        else:
            cnt += a_li[i]
    else:
        print(cnt)

Submission status: Wrong Answer

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

if n == 0:
  if a[0] == 1:
    print(1)
  else:
    print(-1)
else:
  accum = [0]*n
  new_list = list(reversed(a))
  accum[0] = new_list[0]
  for i in range(n-1):
      accum[i+1] = accum[i] + new_list[i+1]
  hat = list(reversed(accum))
  #print(hat)

  b = [1]*(n+1)
  flag = 0
  cand = 0

  for i in range(1,n+1):
    cand = (b[i-1]-a[i-1])*2
    if cand < 1:
      flag = 1
      break
    if cand > hat[i-1]:
      b[i] = hat[i-1]
    else:
      b[i] = cand

  #print(b)
  if flag != 1:
    print(sum(b))
  else:
    print(-1)

Submission status: Wrong Answer

Solution code:

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x


def main():
    from math import ceil
    N = int(input())
    A = list(map(int, input().split()))
    if(A[0] != 0 or A[N] == 0):
        print(-1)
        exit(0)
    # curは作り出せる最大ノード数
    if(N == 0):
        print(-1)
        exit(0)
    if(N == 1 and A[1] != 2):
        print(-1)
        exit(0)
    cur = 0
    S = [0] * (N + 1)
    for i in range(N, 0, -1):
        cur += A[i]
        S[i - 1] = cur
    # print(S)

    ans, cur = 0, 2
    node = [0] * (N + 1)
    a = [0] * (N + 1)
    node[0] = 2
    for i in range(1, N + 1):
        if(A[i] > cur):
            print(-1)
            exit(0)
        if(A[i] > pow(2, i)):
            print(-1)
            exit(0)
        cur = 2 * (cur - A[i])
        node[i] = cur

        if(node[i] > S[i]): node[i] = S[i]
        a[i] = node[i - 1] + cur
        #print("i={}, cur={}".format(i, cur))
    # print(node)
    # print(a)
    # 最初の頂点
    print(sum(node) + 1)
    '''
  cur = 0
  for i in range(N, 0, -1):
      cur += A[i]
      if(cur >= 2**(i - 1)): cur = 2**(i - 1)
      #if(cur >= 2 * A[i - 1]): cur = 2 * A[i - 1]
      ans += cur
      print(cur, ans)
  print(ans)

  '''


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    line = list(map(int,input().split()))
    if n == 0:
        if line[0] != 0:
            return -1
        else:
            return 1
    if line[0] > 0:
        return -1
    front = [0 for i in range(n+1)]
    back = [0 for i in range(n+1)]
    front[0] = 1
    for i in range(n):
        if front[i] * 2 < line[i+1]:
            return -1
        front[i+1] = min(10**30,front[i]*2-line[i+1])
    back[n] = line[n]
    for i in range(n):
        p = n - i - 1
        back[p] = back[p+1] + line[p]
    ans = 0
    for i in range(n):
        ans += line[i]
        ans += min(front[i],back[i]-line[i])
    ans += line[n]
    return ans


print(main())

Submission status: Wrong Answer

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

limit = [0 for i in range(n+1)]
limit[-1] = a[-1]
for i in range(1, n+1):
    limit[-(i+1)] = limit[-i] + a[-(i+1)]

lief = [0 for i in range(n+1)]
root = [0 for i in range(n+1)]
lief[0], root[0] = 1, 1-a[0]

if a[0] == 1:
    print(-1)

else:
    flag = True
    for i in range(1, n+1):
        lief[i] = root[i-1] * 2 if root[i-1] * 2 <= limit[i] else limit[i]
        root[i] = lief[i] - a[i] if i != n else a[i]
        if root[i] <= 0:
            flag = False
            break
    print(sum(lief) if flag else -1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if A[0] == 1:
    print(1)
    exit()

leaf = A
not_leaf = [0] * (N + 1)
not_leaf[0] = 1

for i, a in enumerate(A[1:-1], 1):
    not_leaf[i] = not_leaf[i - 1] * 2 - a

for i in reversed(range(1, N + 1)):
    total = not_leaf[i] + leaf[i]
    prev = not_leaf[i - 1]
    if prev > total:
        not_leaf[i - 1] -= prev - total
    if not_leaf[i - 1] <= 0:
        print(-1)
        break
else:
    print(sum(leaf) + sum(not_leaf))

Submission status: Wrong Answer

Solution code:
from sys import stdin

a=int(stdin.readline())
A=stdin.readline().split()
sum=0
for k in range(0,a+1):
    sum+=int(A[k])

sum-=int(A[a])
ver=1
lay=1
K=0
T=0

if a==0:
    if A[0]!=0:
        print(-1)
        K=1
    else:
        print(1)
        K=1

for l in range(0,a):
    if lay-int(A[l])<=0:
        print(-1)
        K=1
        break
    if (lay-int(A[l]))*2-sum+int(A[l])<=int(A[a]):
        lay=(lay-int(A[l]))*2
        ver+=lay
        sum-=int(A[l])
        T=l
    else:
        lay-=int(A[l])
        sum-=int(A[l])
        x=lay-sum-int(A[a])
        if x==0:
           ver+=lay
        elif x>0:
            print(-1)
            K=1
        else:
           lay=sum+int(A[a])
           ver+=lay
        T=l
        break

if K==0:
    for u in range(T+1,a):
        lay -= int(A[u])
        sum -= int(A[u])
        ver+=lay

if K==0:
    print(ver)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)

if A[0] >= 1:
  print(-1)
  exit()

ret = 1
children = 1

for i in range(N):
    children = children * 2 - A[i+1]
    if children <= 0 and i != N-1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
    print(children)
    print(bottom)
print(ret)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
saidai=[1]*(N+1)
back=[0]*(N+1)
if N!=0:
    ans=0
    saidai[0]=1
    for n in range(1,N+1):
        saidai[n]=saidai[n-1]+saidai[n-1]-A[n-1]-A[n-1]
        if saidai[n]<=0:
            ans=-1
    for n in range(N+1):
        a=N-n
        if a==N:
            back[a]=A[a]
        else:
            back[a]=back[a+1]+A[a]
    if ans!=-1:
        c=0
        for n in range(N+1):
            a=N-n
            if c==0:
                if saidai[a]>back[a]:
                    ans+=back[a]
                else:
                    ans+=saidai[a]
                    c=1
            else:
                ans+=saidai[a]
    print(ans)

else:
    if A[0]==1:
        print(1)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

def main():
    N = int(input())
    list1 = list(map(int, input().split()))
    list2 = [1]*(N+1)

    for i in range(1, N+1):
        list2[i] = list2[i-1]*2 - list1[i]
        if list2[i] < 0:
            return(-1)
          
    list1_ = list(reversed(list1))

    list3 = list(accumulate(list1_))
    list4 = list(reversed(list3))

    count = 0
    finish = 0
    for j in reversed(range(N+1)):
        if list4[j]/2 > list2[j-1]:
            finish = j+1  
            break
        else:
            count += list4[j]
        
    count2 = sum(list1[0:j+1])
    count3 = sum(list2[0:j+1])

    sum1 = count + count2 + count3
    return(sum1)

if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x


def main():
    from math import ceil
    N = int(input())
    A = list(map(int, input().split()))
    if(A[0] != 0 or A[N] == 0):
        print(-1)
        exit(0)
    # curは作り出せる最大ノード数
    if(N == 0 and A[0] == 0):
        print(-1)
        exit(0)
    if(N == 1 and A[1] != 2):
        print(-1)
        exit(0)
    cur = 0
    S = [0] * (N + 1)
    for i in range(N, 0, -1):
        cur += A[i]
        S[i - 1] = cur
    # print(S)

    ans, cur = 0, 2
    node = [0] * (N + 1)
    a = [0] * (N + 1)
    node[0] = 2
    for i in range(1, N + 1):
        if(A[i] > cur):
            print(-1)
            exit(0)
        if(A[i] > pow(2, i)):
            print(-1)
            exit(0)
        cur = 2 * (cur - A[i])
        node[i] = cur

        if(node[i] > S[i]): node[i] = S[i]
        a[i] = node[i - 1] + cur
        #print("i={}, cur={}".format(i, cur))
    # print(node)
    # print(a)
    # 最初の頂点
    print(sum(node) + 1)
    '''
  cur = 0
  for i in range(N, 0, -1):
      cur += A[i]
      if(cur >= 2**(i - 1)): cur = 2**(i - 1)
      #if(cur >= 2 * A[i - 1]): cur = 2 * A[i - 1]
      ans += cur
      print(cur, ans)
  print(ans)

  '''


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
if N == 0:
  if A[0] == 0:
    ans = 1
  else:
    ans = -1
    
elif N == 1:
  if A == [0,2]:
    ans = 3
  else:
    ans = -1

elif N == 2:
  if A == [0,1,1]:
    ans = 4
  elif A == [0,1,2]:
    ans = 5
    
  elif A == [0,0,1]:
    ans = 3
  elif A == [0,0,2]:
    ans = 4
  elif A == [0,0,3]:
    ans = 6
  elif A == [0,0,4]:
    ans = 7
  else:
    ans = -1

else:
  TOP = [0 for _ in range(len(A))]
 
  impossible =0
  TOP[0] = 1
 
  for n in range(len(A)-1):
    max_TOP = TOP[n] * 2 - A[n+1]
 
 
    if n != len(A)-2:
      if max_TOP <= 0:
        impossible = 1
        break
      else:
        TOP[n+1] = max_TOP
    else:
      if max_TOP < 0:
        impossible = 1
        break
      else:
        TOP[-1] = TOP[-2]*2
 
  if impossible == 0:
    if TOP[-1] != A[-1]:
      ans = sum(TOP)+sum(A)-TOP[-1]
      cuts = TOP[N] - A[N] - TOP[N-1]
      for n in range(N,2,-1):
        if cuts <= 0:
          break
        else:
          ans -= cuts
          cuts = cuts- TOP[n-2]
    else:
      ans = sum(TOP)+sum(A)-TOP[-1]
  else:
    ans = -1
  
  
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if A[0] == 1:
    print(1)
    exit()

leaf = A
not_leaf = [0] * (N + 1)
not_leaf[0] = 1

for i, a in enumerate(A[1:-1], 1):
    not_leaf[i] = not_leaf[i - 1] * 2 - a

for i in reversed(range(1, N + 1)):
    total = not_leaf[i] + leaf[i]
    prev = not_leaf[i - 1]
    if prev > total:
        not_leaf[i - 1] -= prev - total
    if not_leaf[i - 1] < 0:
        print(-1)
        break
else:
    print(sum(leaf) + sum(not_leaf))

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
asc = [0] * (n + 1)
desc = [0] * (n + 1)
asc[0] = 1
desc[-1] = a_list[-1]
sum = 0

if a_list[0] != 0:
    print(-1)
    exit()

for i in range(n):
    asc[i + 1] = (asc[i] -a_list[i]) * 2
    desc[n - 1 - i] = desc[n - i] + a_list[n - 1 - i]

for i in range(n + 1):
    num = min(asc[i], desc[i])
    sum += num
    if num < a_list[i]:
        print(-1)
        exit()

print(sum)

Submission status: Wrong Answer

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

R = A[:]
for i in range(N - 1, -1, -1):
    R[i] = R[i + 1] + A[i]
B = 1
ans = B
for i in range(1, N + 1):
    M = 2 * B - A[i]
    if M < 0:
        ans = -1
        break
    B = min(M, max(0, R[i] - A[i]))
    ans += A[i] + B

print(ans if A[0] == 0 else -1)

Submission status: Wrong Answer

Solution code:
def check_valid(A):
    should_zero = False
    for i, a in enumerate(A):
        if should_zero and a != 0:
            return False
        if a > 2 ** i:
            return False
        elif a == 2 ** i:
            should_zero = True
    return True


N = int(input())
A = list(map(int, input().split()))
if not check_valid(A):
    print(-1)
    exit()
elif A[0] == 1:
    print(1)
    exit()

leaf = A
not_leaf = [0] * (N + 1)
not_leaf[0] = 1

for i, a in enumerate(A[1:-1], 1):
    not_leaf[i] = not_leaf[i - 1] * 2 - a

for i in reversed(range(1, N + 1)):
    total = not_leaf[i] + leaf[i]
    prev = not_leaf[i - 1]
    if prev > total:
        not_leaf[i - 1] -= prev - total
    else:
        print(-1)
    if not_leaf[i - 1] < 0:
        print(-1)
        break
else:
    print(sum(leaf) + sum(not_leaf))

Submission status: Wrong Answer

Solution code:
from sys import stdin

a=int(stdin.readline())
A=stdin.readline().split()
sum=0
for k in range(0,a+1):
    sum+=int(A[k])

sum-=int(A[a])
ver=1
lay=1
K=0
T=0

if a==0:
    if A[0]!=0:
        print(-1)
        K=1
    else:
        print(1)
        K=1

for l in range(0,a):
    if lay-int(A[l])<=0:
        print(-1)
        K=1
        break
    if (lay-int(A[l]))*2-sum+int(A[l])<=int(A[a]):
        lay=(lay-int(A[l]))*2
        ver+=lay
        sum-=int(A[l])
        T=l
    else:
        lay-=int(A[l])
        sum-=int(A[l])
        x=lay-sum-int(A[a])
        if x==0:
           ver+=lay
        elif x<0:
           print(-1)
           K=1
           
        else:
           lay=sum+int(A[a])
           ver+=lay
        T=l
        break

if K==0:
    for u in range(T+1,a):
        lay -= int(A[u])
        sum -= int(A[u])
        ver+=lay

if K==0:
    print(ver)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
node=[0]
for i in range(n): 
  node.append((2**i-1-a[i])*2+1)
node.reverse()
a.reverse()
ans=0
flag=True
ha=0
for i in range(n+1):
  ha+=a[i]
  if ha>2**(node[i]):
    ha=2**(node[i])
  if 2**(node[i])<a[i]:
    flag=False
    print(-1)
    break
  ans+=ha

if flag:
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))

l = []

if A[0] != 0:
    print(-1)
    sys.exit()

temp = 1
for i in range(N+1):
    l.append(temp-A[i])
    temp = (temp-A[i])*2

for i in range(N+1):
    if l[i] < 0:
        print(-1)
        sys.exit()

ans = 1
node = 0
for i in range(N, 0, -1):
    if l[i-1] >= node + A[i]:
        node += A[i]
        ans += node
    else:
        ans += node + A[i]
        node = l[i-1]

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
result = 0
ver = []
for n in (reversed(range(0,N+1))):
    if n==len(A)-1:
        ver.append(A[n])
    elif A[n]==0:
        if n**2 < ver[len(A)-n-2]:
            ver.append(int(ver[len(A)-n-2] /2))
        else:
            ver.append(ver[len(A)-n-2])
    elif A[n]!=0:
        if n**2 < ver[len(A)-n-2]:
            ver.append(int(ver[len(A)-n-2] /2) + A[n])
        else:
            ver.append(ver[len(A)-n-2] + A[n])


print(sum(ver))

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))

l = []

if A[0] != 0:
    print(-1)
    sys.exit()

temp = 1
for i in range(N+1):
    l.append(temp-A[i])
    temp = (temp-A[i])*2

for i in range(N+1):
    if l[i] <= 0:
        print(-1)
        sys.exit()

ans = 1
node = 0
for i in range(N, 0, -1):
    if l[i-1] >= node + A[i]:
        node += A[i]
        ans += node
    else:
        ans += node + A[i]
        node = l[i-1]

print(ans)