/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ N + 1 の整数列 A_0, A_1, A_2, \ldots, A_N が与えられます。深さ N の二分木であって、d = 0, 1, \ldots, N に対して深さ d の葉の個数がちょうど A_d であるものは存在するでしょうか？存在する場合はそのような二分木の頂点数の最大値を、存在しない場合は -1 を出力してください。
注釈
- 二分木とは、根付き木であって、それぞれの頂点の (直接の) 子の個数が 2 以下であるものを指す。
- 根付き木の葉とは、子の個数が 0 である頂点を指す。
- 根付き木の頂点 v の深さとは、根付き木の根から v までの距離を指す。(根の深さは 0 である。)
- 根付き木の深さとは、根付き木の頂点の深さの最大値を指す。
制約
- 0 \leq N \leq 10^5
- 0 \leq A_i \leq 10^{8} (0 \leq i \leq N)
- A_N \geq 1
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_0 A_1 A_2 \cdots A_N
出力
答えを整数で出力せよ。
入力例 1
3 0 1 1 2
出力例 1
7
以下の二分木が最善です。この二分木の頂点数は 7 であるため、7 を出力します。
入力例 2
4 0 0 1 0 2
出力例 2
10
入力例 3
2 0 3 1
出力例 3
-1
入力例 4
1 1 1
出力例 4
-1
入力例 5
10 0 0 1 1 2 3 5 8 13 21 34
出力例 5
264
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