B - とても長い数列
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は長さ N の数列 A = \{A_1, A_2, ..., A_N\} を用意しました。高橋君は数列 A を元に「とても長い数列」を、以下のような手順で作ろうとしています。
- まず長さ 0 の数列を用意し、これを S と呼ぶことにする。
- S、A_1、S をこの順につなげた数列を新たな S とする。
- S、A_2、S をこの順につなげた数列を新たな S とする。
- (中略)
- S、A_N、S をこの順につなげた数列を新たな S とする。
- この時点での S を「とても長い数列」とする。
例えば N = 3, A_1 = 1, A_2 = 2, A_3 = 3 なら、S は \{\} → \{1\} → \{1,2,1\} → \{1,2,1,3,1,2,1\} と変化し、「とても長い数列」は \{1,2,1,3,1,2,1\} となります。
高橋君はこの手順によって作られる「とても長い数列」に含まれる数の和を知りたがっています。これを高橋君の代わりに計算するプログラムを作成してください。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
- 1 行目には、整数 N (1 ≦ N ≦ 30) が与えられる。
- 2 行目には、N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目には、整数 A_i (0 ≦ A_i ≦ 100) が与えられる。
- 「とても長い数列」に含まれる数の和は 10^9 以下となることが保証されている。
出力
「とても長い数列」に含まれる数の和を 1 行に出力せよ。出力の末尾に改行を入れること。
部分点
この問題には部分点が設定されている。
- N ≦ 10 を満たすデータセットに正解した場合は、60 点が与えられる。
- 追加の制約のないデータセットに正解した場合は、上記とは別に 40 点が与えられる。
入力例1
3 1 2 3
出力例1
11
この入力例は問題文中の例と同じです。
「とても長い数列」は \{1,2,1,3,1,2,1\} となり、1+2+1+3+1+2+1 = 11 であるため 11 を出力します。
入力例2
8 0 1 3 6 12 25 50 100
出力例2
652
入力例3
30 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力例3
536870912
「とても長い数列」はとても長くなることがあるので注意してください。