Problem:


1年生 (A First Grader)

問題

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君が作り，確かめることができる正しい等式の個数は 231-1 を超えない．また，与えられる入力データの全てにおいて，JOI君が作り，確かめることができる正しい等式の個数は 263-1 を超えない． 

出力

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

入出力例

入力例 1
  

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

出力例 1

10

入力例 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
  

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

出力例 2

7069052760

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

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
11
8 3 2 4 8 7 2 4 0 8 8


Sample output:
10

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from collections import defaultdict

N = int(input())
nums = [int(num) for num in input().split()]

calc_table = {0:1}
for num in nums[:-1]:#last num is rhs
    new_calc_table = defaultdict(int)
    for calcs,patterns in calc_table.items():
        if (calcs+num <= 20):
            new_calc_table[calcs+num] = new_calc_table.get(calcs+num,0) + patterns
        if (calcs-num >=  0):
            new_calc_table[calcs-num] = new_calc_table.get(calcs-num,0) + patterns
    calc_table = new_calc_table

print(str(calc_table[nums[-1]]))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from collections import defaultdict

N = int(input())
lhs = [int(num) for num in input().split()]
lhs_first = lhs.pop(0)
rhs = lhs.pop()

calc_table = {lhs_first:1}
for num in lhs:#last num is rhs
    new_calc_table = defaultdict(int)
    for calcs,patterns in calc_table.items():
        if (calcs+num <= 20):
            new_calc_table[calcs+num] = new_calc_table.get(calcs+num,0) + patterns
        if (calcs-num >=  0):
            new_calc_table[calcs-num] = new_calc_table.get(calcs-num,0) + patterns
    calc_table = new_calc_table
    print(str(dict(calc_table)))

print(str(calc_table[rhs]))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import os
import sys
import itertools

if __name__ == '__main__':
    a = int(raw_input())
    l = map(int, raw_input().split())

    dp = [[ 0 for _ in xrange(21)] for _ in xrange(len(l))]
    dp[0][0] = 1

    for j in xrange(len(l)-1):
        for i in xrange(21):
            if 0 <= i+l[j] <= 20: dp[j+1][i+l[j]] += dp[j][i]
            if 0 <= i-l[j] <= 20: dp[j+1][i-l[j]] += dp[j][i]

    print dp[-1][l[-1]]

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import os
import sys
import itertools

if __name__ == '__main__':
    a = int(raw_input())
    l = map(int, raw_input().split())

    dp = [[ 0L for _ in xrange(21)] for _ in xrange(len(l))]
    dp[0][0] = 1

    for j in xrange(len(l)-1):
        for i in xrange(21):
            if 0 <= i+l[j] <= 20: dp[j+1][i+l[j]] += dp[j][i]
            if 0 <= i-l[j] <= 20: dp[j+1][i-l[j]] += dp[j][i]

    print dp[-1][l[-1]]

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
ns=map(int,raw_input().split())
dp=[[0]*21 for _ in xrange(n)]
dp[0][0]=1
for i in xrange(n-1):
    for j in xrange(21):
        if j-ns[i]>=0 and j+ns[i]<=20:
            dp[i+1][j]=dp[i][j-ns[i]]+dp[i][j+ns[i]]
        elif j-ns[i]>=0:
            dp[i+1][j]=dp[i][j-ns[i]]
        else:
            dp[i+1][j]=dp[i][j+ns[i]]
print(dp[n-1][ns[-1]])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * 21 for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for j in range(21):
        if dp[i][j] == 0:
            continue
        if 0 <= j + a[i] <= 20:
            dp[i + 1][j + a[i]] += dp[i][j]
        if 0 <= j - a[i] <= 20:
            dp[i + 1][j - a[i]] += dp[i][j]
print(dp[n][0])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * 21 for i in range(n)]
dp[0][0] = 1
for i in range(n - 1):
    for j in range(21):
        if 0 <= j + a[i] <= 20:
            dp[i + 1][j + a[i]] += dp[i][j]
        if 0 <= j - a[i] <= 20:
            dp[i + 1][j - a[i]] += dp[i][j]
print(dp[n - 1][a[n - 1]])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * 21 for i in range(n)]
dp[0][0] = 1
for i in range(n - 1):
    for j in range(21):
        if dp[i][j] == 0:
            continue
        if 0 <= j + a[i] <= 20:
            dp[i + 1][j + a[i]] += dp[i][j]
        if 0 <= j - a[i] <= 20:
            dp[i + 1][j - a[i]] += dp[i][j]
print(dp[n - 1][a[n - 1]])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * 21 for i in range(n)]
dp[0][a[0]] = 1
for i in range(n - 1):
    for j in range(21):
        if dp[i][j] == 0:
            continue
        if 0 <= j + a[i + 1] <= 20:
            dp[i + 1][j + a[i + 1]] += dp[i][j]
        if 0 <= j - a[i] <= 20:
            dp[i + 1][j - a[i + 1]] += dp[i][j]
print(dp[n - 2][a[n - 1]])

Submission status: Wrong Answer

Solution code:
N=int(input())
number=[int(i) for i in input().split(" ")]
a=number.pop(-1)

numbermap=[[0 for i in range(21)] for j in range(N)]

numbermap[0][0]=1

for i in range(N-1):
    for j in range(21):
        try:
            numbermap[i+1][j+number[i]]+=numbermap[i][j]
        except:
            pass
        try:
            if j-number[i]>=0:
                numbermap[i+1][j-number[i]]+=numbermap[i][j]
        except:
            pass


print (numbermap[-1][a])

Submission status: Wrong Answer

Solution code:
#dp[i][j]...i番で作れるjの通り数
#出力はdp[n][m]

n = int(input())
A = list(map(int,input().split()))
m = A.pop()
maxN = sum(A)
dp = [[0 for i in range(maxN + 1)] for _ in A]
for i in range(len(A)):
  for j in range(maxN + 1):
    if i == 0:
      dp[0][A[i]] = 1
    else:
      if j - A[i] >= 0:
        dp[i][j] += dp[i - 1][j - A[i]]
      if j + A[i] <= maxN:
        dp[i][j] += dp[i - 1][j + A[i]]

print(dp[len(A) - 1][m])

Submission status: Accepted

Solution code:
FINGER_MAX = 21
N = int(raw_input())
num = [int(x) for x in raw_input().split(' ')]
table = [[0 for j in range(FINGER_MAX)] for i in range(N)]
table[0][num[0]] = 1

for i in range(1, N-1):
    n = num[i]
    for j in range(FINGER_MAX):
        if j + n < FINGER_MAX:
            table[i][j+n] += table[i-1][j]
        if j - n > -1:
            table[i][j-n] += table[i-1][j]
print table[N-2][num[-1]]

Submission status: Accepted

Solution code:
N = int(input())

pre_c = [0 for i in range(21)]
for i,n in enumerate(map(int,input().split())):
    if i == 0:
        pre_c[n] = 1
    elif i < N-1:
        next_c = [0 for i in range(21)]
        for j,p in enumerate(pre_c):
            if p > 0:
                if 0 <= j+n <= 20:
                    next_c[j+n] += p
                if 0 <= j-n <= 20:
                    next_c[j-n] += p

        pre_c = next_c
    else:
        print(pre_c[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from collections import defaultdict

N = int(input())
lhs = [int(num) for num in input().split()]
lhs_first = lhs.pop(0)
rhs = lhs.pop()

calc_table = {lhs_first:1}
for num in lhs:#last num is rhs
    new_calc_table = defaultdict(int)
    for calcs,patterns in calc_table.items():
        if (calcs+num <= 20):
            new_calc_table[calcs+num] = new_calc_table.get(calcs+num,0) + patterns
        if (calcs-num >=  0):
            new_calc_table[calcs-num] = new_calc_table.get(calcs-num,0) + patterns
    calc_table = new_calc_table

print(str(calc_table[rhs]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())
lhs = [int(num) for num in input().split()]
lhs_first = lhs.pop(0)
rhs = lhs.pop()

calc_table = [0 for _ in range(21)]
calc_table[lhs_first] = 1
for num in lhs:
    new_calc_table = [0 for _ in range(21)]
    for calcs,patterns in enumerate(calc_table):
        if (calcs+num <= 20):
            new_calc_table[calcs+num] += patterns
        if (calcs-num >=  0):
            new_calc_table[calcs-num] += patterns
    calc_table = new_calc_table

print(str(calc_table[rhs]))

Submission status: Accepted

Solution code:
n = input()
m = map(int, raw_input().split())
memo = [[0]*21 for i in range(n-1)]
memo[0][m[0]] = 1
for i in range(1,n-1):
    for k in range(21):
        if 0 <= k + m[i] <= 20:
            memo[i][k + m[i]] += memo[i-1][k]
        if 0 <= k - m[i] <= 20:
            memo[i][k - m[i]] += memo[i-1][k]
print memo[n-2][m[n-1]]

Submission status: Accepted

Solution code:
#!/usr/bin/python

import os
import sys
import itertools

if __name__ == '__main__':
    a = int(raw_input())
    l = map(int, raw_input().split())

    dp = [[ 0L for _ in xrange(21)] for _ in xrange(len(l))]
    dp[1][l[0]] = 1

    for j in xrange(1,len(l)-1):
        for i in xrange(21):
            if 0 <= i+l[j] <= 20: dp[j+1][i+l[j]] += dp[j][i]
            if 0 <= i-l[j] <= 20: dp[j+1][i-l[j]] += dp[j][i]

    print dp[-1][l[-1]]

Submission status: Accepted

Solution code:
N=int(raw_input())
numbers=[int(x) for x in raw_input().split()]
mat=[[0 for x in range(21)] for y in range(N)]
mat[0][numbers[0]]=1
fin=numbers[-1]
for i in range(1,N-1):
    n=numbers[i]
    for j in range(21):
        if j+n<21:
            mat[i][j+n]+=mat[i-1][j]
        if j-n>-1:
            mat[i][j-n]+=mat[i-1][j]
print mat[N-2][fin]

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve(n, l, ans):
    table = [[0] * 21 for _ in xrange(n-1)]
    table[0][l[0]] = 1
    for i in xrange(1, n-1):
        for j in xrange(0, 21):
            if j - l[i] < 0:
                table[i][j] = table[i-1][j+l[i]]
            elif j + l[i] > 20:
                table[i][j] = table[i-1][j-l[i]]
            else:
                table[i][j] = table[i-1][j-l[i]] + table[i-1][j+l[i]]
    print table[n-2][ans]

if __name__ == "__main__":
    n = int(raw_input())
    l = map(int, raw_input().split())
    ans = l.pop()
    solve(n, l, ans)

Submission status: Accepted

Solution code:
raw_input()
xs = [int(x) for x in raw_input().split()]
a = xs.pop()
dp = [0] * 21
dp[xs[0]] = 1

for x in xs[1:]:
    ndp = [0] * 21
    for n, c in enumerate(dp):
        for nn in [n+x, n-x]:
            if 0 <= nn < 21:
                ndp[nn] += c
    dp = ndp

print dp[a]

Submission status: Accepted

Solution code:
n=int(raw_input())
ns=map(int,raw_input().split())
dp=[[0]*21 for _ in xrange(n)]
for i in xrange(n-1):
    for j in xrange(21):
        if i==0:
            if ns[i]==j:
                dp[i+1][j]=1
                break
            continue
        if j-ns[i]>=0 and j+ns[i]<=20:
            dp[i+1][j]=dp[i][j-ns[i]]+dp[i][j+ns[i]]
        elif j-ns[i]>=0:
            dp[i+1][j]=dp[i][j-ns[i]]
        else:
            dp[i+1][j]=dp[i][j+ns[i]]
print(dp[n-1][ns[-1]])

Submission status: Accepted

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

## dp[i][j]: i???????????°????????§??§j????????????????????°
dp = [[0 for j in range(21)] for i in range(N-1)]

dp[0][a[0]] = 1
for i in range(1, N-1):
    for j in range(21):
        if (j - a[i]) in range(21):
            dp[i][j] += dp[i-1][j-a[i]]
        if (j + a[i]) in range(21):
            dp[i][j] += dp[i-1][j+a[i]]
        
print(dp[N-2][a[N-1]])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * 21 for i in range(n - 1)]
dp[0][a[0]] = 1
for i in range(1, n - 1):
    for j in range(21):
        if 0 <= j + a[i] <= 20:
            dp[i][j] += dp[i - 1][j + a[i]]
        if 0 <= j - a[i] <= 20:
            dp[i][j] += dp[i - 1][j - a[i]]
print(dp[n - 2][a[n - 1]])

Submission status: Accepted

Solution code:
N=int(input())
number=[int(i) for i in input().split(" ")]
a=number.pop(-1)

if number[0]==0:
    N-=1
    number.pop(0)


numbermap=[[0 for i in range(21)] for j in range(N)]

numbermap[0][0]=1

for i in range(N-1):
    for j in range(21):
        if j+number[i]<=20:
            numbermap[i+1][j+number[i]]+=numbermap[i][j]
        if j-number[i]>=0:
            numbermap[i+1][j-number[i]]+=numbermap[i][j]



print (numbermap[-1][a])

Submission status: Accepted

Solution code:
#dp[i][j]...i番で作れるjの通り数
#出力はdp[n][m]

n = int(input())
A = list(map(int,input().split()))
m = A.pop()
maxN = min(sum(A), 20)
dp = [[0 for i in range(maxN + 1)] for _ in A]
for i in range(len(A)):
  for j in range(maxN + 1):
    if i == 0:
      dp[0][A[i]] = 1
    else:
      if j - A[i] >= 0:
        dp[i][j] += dp[i - 1][j - A[i]]
      if j + A[i] <= maxN:
        dp[i][j] += dp[i - 1][j + A[i]]

print(dp[len(A) - 1][m])

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
d=[[0]*21 for i in[0]*~-N]
d[0][a[0]]=1
for i in range(1,N-1):
 for j in range(21):
  if j+a[i]<21:d[i][j]=d[i-1][j+a[i]]
  if 0<=j-a[i]:d[i][j]+=d[i-1][j-a[i]]
print(d[N-2][a[N-1]])

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
d=[[0]*21 for i in[0]*~-N]
d[0][a[0]]=1
for i in range(1,N-1):
 for j in range(21):
  d[i][j]=(21>j+a[i]and d[i-1][j+a[i]])+(0<=j-a[i]and d[i-1][j-a[i]])
print(d[N-2][a[N-1]])

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
d=[[0]*21 for _ in[0]*~-N]
d[0][a[0]]=1
for i in range(1,N-1):
 for j in range(21):
  d[i][j]=(21>j+a[i]and d[i-1][j+a[i]])+(0<=j-a[i]and d[i-1][j-a[i]])
print(d[N-2][a[N-1]])

Submission status: Accepted

Solution code:
N=int(input())
a=[*map(int,input().split())]
d=[[0]*21 for _ in[0]*~-N]
d[0][a[0]]=1
for i in range(1,N-1):
 for j in range(21):
  d[i][j]=(21>j+a[i]and d[i-1][j+a[i]])+(0<=j-a[i]and d[i-1][j-a[i]])
print(d[N-2][a[N-1]])

Submission status: Accepted

Solution code:
N=int(input())
a=[*map(int,input().split())]
d=[[0]*21 for _ in[0]*~-N]
d[0][a[0]]=1
for i in range(1,N-1):
 for j in range(21):
  d[i][j]=(21>j+a[i]and d[i-1][j+a[i]])+(j>=a[i]and d[i-1][j-a[i]])
print(d[N-2][a[N-1]])

Submission status: Accepted

Solution code:
# AOJ 0557: A First Grader
# Python3 2018.6.30 bal4u

p = [[0 for j in range(21)] for i in range(2)]
n = int(input())
d = list(map(int, input().split()))
p[0][d[0]] = 1
s = d[n-1]
for i in range(1, n):
	x = d[i];
	for j in range(21): p[i&1][j] = 0
	for j in range(21-x): p[i&1][j+x] += p[1-(i&1)][j]
	for j in range(x, 21): p[i&1][j-x] += p[1-(i&1)][j];
print(p[n&1][s])

Submission status: Accepted

Solution code:
n = input()
s = map(int, raw_input().split())
ans = s[-1]
dp = [[0] * 21 for i in range(n)]
dp[0][s[0]] = 1
for i in range(1, n-1):
    for j in range(21):
        if dp[i-1][j] == 0: continue
        vp = j + s[i]
        vm = j - s[i]
        if vp <= 20:
            dp[i][vp] += dp[i-1][j]
        if 0 <= vm:
            dp[i][vm] += dp[i-1][j]
print dp[n-2][ans]

Submission status: Accepted

Solution code:
n = input()
L = map(int, raw_input().split())
dp = [[0] * 21 for _ in xrange(n)]
dp[0][L[0]] = 1
for i in xrange(1, n):
    for j in xrange(21):
        if j - L[i] >= 0:
            dp[i][j - L[i]] += dp[i - 1][j]
        if j + L[i] <= 20:
            dp[i][j + L[i]] += dp[i - 1][j]
print dp[n - 1][0]

Submission status: Accepted

Solution code:
#coding:utf-8
from __future__ import division,print_function
try:
    input = raw_input
except NameError:
    pass
# 上記のコードはPython2とPython3の違いを一部吸収するためのもの

# N * Mの表をつくる.すべての要素はvにする。
def make_matrix(N,M,v):
    # return [[v for i in range(M)] for j in range(N)]とも書ける。
    ret = []
    for i in range(N):
        l = []
        for j in range(M):
            l.append(v)
        ret.append(l)
    return ret


def solve(numbers):
    MAX_NUMBER = 20
    SIGN = [-1,+1]
    rightside_of_expression = numbers[-1]
    leftside_of_expession = numbers[:-1]

    # (N-1) * 21 の表
    #  way_to_make[i][j] = i項まで使ってjをつくる+/-の組み合わせ
    way_to_make = make_matrix(len(leftside_of_expession),MAX_NUMBER+1,0)

    # インデックスを使いたいので直接 for i in leftside_of_expessionとはしない。
    #  enumerateをつかっても良い
    for i in range(len(leftside_of_expession)):
        v = leftside_of_expession[i]
        # 最初の項は+しかない。
        if i == 0:
            way_to_make[0][v] = 1
        else:
            for j in range(MAX_NUMBER+1):
                # way_to_make[i][j] = way_to_make[i-1][j-numbers[i]]
                #                   + way_to_make[i-1][j+numbers[i]]
                for s in SIGN:
                    p = j + s*numbers[i]
                    if 0 <= p <= MAX_NUMBER:
                        way_to_make[i][j] += way_to_make[i-1][p]

    return way_to_make[-1][rightside_of_expression]

def main():
    N = int(input())

    string_of_numbers = input().split(" ")
    numbers = []
    for s in string_of_numbers:
        numbers.append(int(s))

    # solveはNを必要としない。(N = len(numbers)だから。)
    print(solve(numbers))

main()

Submission status: Accepted

Solution code:
n = input()
arr = map(int, raw_input().split())
answer = arr[n-1]

dp = [[0]*21 for i in range(n)]
dp[0][arr[0]] = 1

for i in range(1, n-1):
  for j in range(21):
    if dp[i-1][j] == 0: continue
    vp = j + arr[i]
    vm = j - arr[i]

    if vp <= 20:
      dp[i][vp] += dp[i-1][j]
    if vm >= 0:
      dp[i][vm] += dp[i-1][j]

print dp[n-2][answer]

Submission status: Accepted

Solution code:
_ = raw_input()
nums = [int(x) for x in raw_input().split(" ")]
x = nums.pop()

res_ = [0 for i in range(21)]
res_[nums[0]] = 1
nums = nums[1:]

for n in nums:
	res = [0 for i in range(21)]
	for (i, r) in enumerate(res_):
		if r > 0:
			if 0 <= i-n <= 20:
				res[i-n] += r
			if 0 <= i+n <= 20:
				res[i+n] += r
	res_ = res

print "%d" % res_[x]

Submission status: Accepted

Solution code:
N = int(input())
dp = [ [0]*(21) for _ in range(N) ]
lst = list(map(int,input().split()))
dp[0][0] = 1

for i in range(N-1):
  for j in range(21):
    a = lst[i]
    if i==j==a==0:
      dp[i+1][j] = 1
    else:
      if dp[i][j] > 0:
        if j-a >= 0:
          dp[i+1][j-a] += dp[i][j]
        if j+a <= 20:
          dp[i+1][j+a] += dp[i][j]

print(dp[-1][lst[-1]])

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


MIN = 0
MAX = 20
SIZE = 21

N = int(input())
dp = [[0]*SIZE for _ in range(N-1)]

table = list(map(int,input().split()))

dp[0][table[0]] = 1

for i in range(1,N-1):
    for k in range(MIN,MAX+1):
        if dp[i-1][k] == 0:
            continue
        if k+table[i] <= MAX:
            dp[i][k+table[i]] += dp[i-1][k]
        if k-table[i] >= MIN:
            dp[i][k-table[i]] += dp[i-1][k]

print("%d"%(dp[N-2][table[N-1]]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
A First Grader
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557

"""
import sys
from collections import Counter


def solve(numbers):
    status = Counter({numbers[0]: 1})
    for n in numbers[1:-1]:
        u = Counter()
        for k, v in status.items():
            u[k+n] += v * (0 <= k + n <= 20)
            u[k-n] += v * (0 <= k - n <= 20)
        status = Counter({k: v  for k, v in u.items() if v > 0})
    return status[numbers[-1]]


def main(args):
    input()
    numbers = [int(n) for n in input().split()]
    ans = solve(numbers)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def run():
  N = int(input())
  n_li = [int(i) for i in input().split()]
  dp = [[0]*21 for _ in range(N-1)]
  dp[0][n_li[0]] = 1
  n_last = n_li[-1]
  for i in range(N-2):
    next_value = n_li[i+1]
    for num in range(21):
      if dp[i][num] > 0:
        sum1 = num + next_value
        sum2 = num - next_value
        if (sum1 >= 0) and (sum1 <= 20):
          dp[i+1][sum1] += dp[i][num]
        if (sum2 >= 0) and (sum2 <= 20):
          dp[i+1][sum2] += dp[i][num]
  print(dp[-1][n_last])
      
if __name__ == '__main__':
  run()

Submission status: Accepted

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

dp = [[0 for _ in range(1100)] for _ in range(110)]

last = a[-1]

dp[0][0] = 1

for i in range(n):
    for j in range(100):
        if i == 0:
            dp[i + 1][a[i]] = 1

        # +
        if 0 <= j + a[i] <= 20:
            dp[i + 1][j + a[i]] += dp[i][j]
        # -
        if 0 <= j - a[i] <= 20:
            dp[i + 1][j - a[i]] += dp[i][j]

print(dp[n - 1][last])

Submission status: Accepted

Solution code:
n = int(input())
nums = [int(i) for i in input().split()]
dp = [[0 for j in range(21)] for i in range(n - 1)]

dp[0][nums[0]] = 1
for i in range(0, n - 2):
    for j in range(0, 21):
        if j + nums[i + 1] <= 20:
            dp[i + 1][j + nums[i + 1]] += dp[i][j]
        if j - nums[i + 1] >= 0:
            dp[i + 1][j - nums[i + 1]] += dp[i][j]

print(dp[n - 2][nums[n - 1]])

Submission status: Accepted

Solution code:
MAX = 21
N = int(input())
num = [int(x) for x in input().split()]
table = [[0 for _ in range(MAX)] for _ in range(N - 1)]

table[0][num[0]] = 1

for i in range(1, N-1):
	n = num[i]
	for j in range(MAX):
		if j + n < MAX:
			table[i][j+n] += table[i-1][j]
		if j - n > -1:
			table[i][j-n] += table[i-1][j]

print(table[-1][num[-1]])

Submission status: Accepted

Solution code:
n = int(input())
num=[int(num) for num in input().split()]
kazu = [[0 for i in range(n+1)] for j in range(21)]
kazu[num[0]][0]=1
for i in range(n-1):
    if i>0:
        for j in range(21):
            if j - num[i] >= 0 and j - num[i] <= 20:
                kazu[j][i] = kazu[j][i] + kazu[j-num[i]][i-1]
            if j + num[i] >= 0 and j + num[i] <= 20:
                kazu[j][i] = kazu[j][i] + kazu[j+num[i]][i-1]
print(kazu[num[n-1]][n-2])

Submission status: Accepted

Solution code:
from collections import defaultdict
N=int(input())
A=list(map(int,input().split()))
a=A[-1]
A=A[:-1]
dp=[[0]*21 for i in range(N)]
#dp[ii[j]コメまででjになる個数
dp[0][0]=1
for i in range(1,N):
    for j in range(21):
        if i==1:
            dp[i][A[i-1]]=1
        if j-A[i-1]>=0:
            dp[i][j]+=dp[i-1][j-A[i-1]]
        if j+A[i-1]<=20:
            dp[i][j]+=dp[i-1][j+A[i-1]]
print(dp[N-1][a])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
max_A = sum(A) - A[-1]
dp = [[0 for _ in range(max_A+1)] for _ in range(N+1)]
dp[0][A[0]] = 1

for i in range(1, N-1):
    for sum_A in range(max_A+1):
        if 0 <= sum_A - A[i] <= 20:
            dp[i][sum_A] += dp[i-1][sum_A-A[i]]
        if sum_A + A[i] <= 20:
            dp[i][sum_A] += dp[i-1][sum_A+A[i]]

print(dp[N-2][A[-1]])

Submission status: Accepted

Solution code:
import operator

n = int(input())
series = list(map(int, input().split()))

frame = [0]*21

def new_frame(shift):
    global frame
    if shift == 0:
        new_frame = list(map(operator.mul, frame, [2]*21))
    else:
        plus = [0]*shift + frame[:-shift]
        minus = frame[shift:] + [0]*shift
        new_frame = list(map(operator.add, plus, minus))
    return new_frame

frame[series[0]] = 1

for i in range(1,n-1):
    frame = new_frame(series[i])
else:
    print(frame[series[-1]])

Submission status: Runtime Error

Solution code:
while True:
    N = int(input())
    if N == 0:
        break
    a = list(map(int, input().split()))

    ## dp[i][j]: i???????????°????????§??§j????????????????????°
    dp = [[0 for j in range(21)] for i in range(N-1)]

    dp[0][a[0]] = 1
    for i in range(1, N-1):
        for j in range(21):
            if (j - a[i]) in range(21):
                dp[i][j] += dp[i-1][j-a[i]]
            if (j + a[i]) in range(21):
                dp[i][j] += dp[i-1][j+a[i]]
            
    print(dp[N-2][a[N-1]])

Submission status: Runtime Error

Solution code:
while True:
    N = int(input())
    if N == 0:
        break
    a = list(map(int, input().split()))

    dp = [[0 for j in range(21)] for i in range(N-1)]

    dp[0][a[0]] = 1
    for i in range(1, N-1):
        for j in range(21):
            if (j - a[i]) in range(21):
                dp[i][j] += dp[i-1][j-a[i]]
            if (j + a[i]) in range(21):
                dp[i][j] += dp[i-1][j+a[i]]
            
    print(dp[N-2][a[N-1]])

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * 21 for i in range(n)]
dp[0][0] = 1
for i in range(n - 1):
    for j in range(21):
		if dp[i][j] == 0:
			continue
        if 0 <= j + a[i] <= 20:
            dp[i + 1][j + a[i]] += dp[i][j]
        if 0 <= j - a[i] <= 20:
            dp[i + 1][j - a[i]] += dp[i][j]
print(dp[n - 1][a[n - 1]])

Submission status: Runtime Error

Solution code:
def calc(num,ans):
    if len(num)==1:
        if num[0]==ans:
            return 1
        else:
            return 0
    else:
        a=num.copy()
        x=a.pop(-1)
        if ans-x>=0 and ans+x<=20:
            return calc(a,ans-x)+calc(a,ans+x)
        elif ans-x>=0:
            return calc(a,ans-x)
        elif ans+x<=20:
            return calc(a,ans+x)
        else:
            return 0

N=int(input())
number=[int(i) for i in input().split(" ")]
a=number.pop(-1)
print(calc(number,a))

Submission status: Runtime Error

Solution code:
n = int(input)
inp = input()
nums = [int(i) for i in inp.split()]
ans = nums[-1]

dp = [[0 for j in range(21)] for i in range(n)]
dp[0][nums[0]] = 1

for i in range(1,n-1):
    for j in range(21):
        if dp[i-1][j] == 0:
            continue
        p = j + nums[i]
        if p <= 20:
            dp[i][p] += dp[i-1][j]

        m = j - nums[i]
        if m >= 0:
            dp[i][m] += dp[i-1][j]

print(dp[n-2][ans])

Submission status: Runtime Error

Solution code:
n = int(input)
nums = [int(i) for i in input().split()]
ans = nums[-1]

dp = [[0 for j in range(21)] for i in range(n)]
dp[0][nums[0]] = 1

for i in range(1,n-1):
    for j in range(21):
        if dp[i-1][j] == 0:
            continue
        p = j + nums[i]
        if p <= 20:
            dp[i][p] += dp[i-1][j]

        m = j - nums[i]
        if m >= 0:
            dp[i][m] += dp[i-1][j]

print(dp[-1][ans])

Submission status: Runtime Error

Solution code:
n = input()
s = map(int, raw_input().split())
ans = s[-1]
dp = [[0] * 21 for i in range(n)]
dp[0][s[0]] = 1
for i in range(1, n-1):
    for j in range(21):
        if dp[i-1][j] == 0: continue
        vp = j + s[i]
        vm = j - s[i]
        if vp <= 20:
            dp[i][vp] += dp[i-1][j]
        if 0 <= vm:
            dp[i][vm] += dp[i-1][j]
print dp[n-2][ans