第10回日本情報オリンピック　予選４

2010年12月19日
情報オリンピック日本委員会

問題

JOI君は小学 1 年生である．JOI君は教わったばかりの足し算，引き算がとても好きで，数字が並んでいるのを見ると最後の 2 つの数字の間に「=」を入れ，残りの数字の間に必ず「+」または「-」を入れて等式を作って遊んでいる．例えば「8 3 2 4 8 7 2 4 0 8 8」から，等式「8+3-2-4+8-7-2-4-0+8=8」を作ることができる．

JOI君は等式を作った後，それが正しい等式になっているかを計算して確かめる．ただし，JOI君はまだ負の数は知らないし，20 を超える数の計算はできない．したがって，正しい等式のうち左辺を左から計算したとき計算の途中で現れる数が全て 0 以上 20 以下の等式だけがJOI君が確かめられる正しい等式である．例えば，「8+3-2-4-8-7+2+4+0+8=8」は 正しい等式だが，途中に現れる 8+3-2-4-8 が負の数なのでJOI君はこの等式が正しいかどうか確かめることができない．

入力として数字の列が与えられたとき，JOI君が作り，確かめることができる正しい等式の個数を求めるプログラムを作成せよ．

入力

入力ファイルは 2 行からなる．1 行目には並んでいる数字の個数を表す整数 N （3 ≦ N ≦ 100）が書かれている．2 行目には 0 以上 9 以下の整数が N 個，空白を区切りとして書かれている．

与えられる入力データの 60% では，JOI君が作り，確かめることができる正しい等式の個数は 2³¹-1 を超えない．また，与えられる入力データの全てにおいて，JOI君が作り，確かめることができる正しい等式の個数は 2⁶³-1 を超えない．

出力

JOI君が作り，確かめることができる正しい等式の個数を表す整数を 1 行で出力せよ．

入出力例

11
8 3 2 4 8 7 2 4 0 8 8
  

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1
   

10
  

7069052760
  

入力例 1 において，JOI君は 10 個の正しい等式

8+3-2-4+8-7-2-4-0+8=8

8+3-2-4+8-7-2-4+0+8=8

8+3+2+4-8-7+2-4-0+8=8

8+3+2+4-8-7+2-4+0+8=8

8+3+2-4+8-7+2+4-0-8=8

8+3+2-4+8-7+2+4+0-8=8

8-3+2+4-8+7+2+4-0-8=8

8-3+2+4-8+7+2+4+0-8=8

8-3+2-4+8+7+2-4-0-8=8

8-3+2-4+8+7+2-4+0-8=8

を作り，確かめることができるので 10 を出力する．

入力例 2 において，答えが 32 bit符号付き整数の範囲に収まらないことに注意せよ．

（2015年2月21日追記） 利用者からの指摘で，入力例 1 の説明中の等式の中に誤りがあることが判明しました． 現在は修正済です．5 番目の等式は 8+3-2-4+8-7+2+4-0-8=8 でしたが，これを 8+3+2-4+8-7+2+4-0-8=8 に修正しました． また，6 番目の等式は 8+3-2-4+8-7+2+4+0-8=8 でしたが，これを 8+3+2-4+8-7+2+4+0-8=8 に修正しました．

※各入出力例のデータは， 右クリック等によりファイルに保存して利用可能です．

採点用データ