Problem:


Score : 300 points

Problem Statement

Tak has N cards. On the i-th (1 \leq i \leq N) card is written an integer x_i.
He is selecting one or more cards from these N cards, so that the average of the integers written on the selected cards is exactly A.
In how many ways can he make his selection?

Constraints

1 \leq N \leq 50

1 \leq A \leq 50

1 \leq x_i \leq 50

N,\,A,\,x_i are integers.

Partial Score

200 points will be awarded for passing the test set satisfying 1 \leq N \leq 16.

Input

The input is given from Standard Input in the following format:

N A
x_1 x_2 ... x_N

Output

Print the number of ways to select cards such that the average of the written integers is exactly A.

Sample Input 1

4 8
7 9 8 9

Sample Output 1

5

The following are the 5 ways to select cards such that the average is 8:

Select the 3-rd card.

Select the 1-st and 2-nd cards.

Select the 1-st and 4-th cards.

Select the 1-st, 2-nd and 3-rd cards.

Select the 1-st, 3-rd and 4-th cards.

Sample Input 2

3 8
6 6 9

Sample Output 2

0

Sample Input 3

8 5
3 6 2 8 7 6 5 9

Sample Output 3

19

Sample Input 4

33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

Sample Output 4

8589934591

The answer may not fit into a 32-bit integer.



Sample input:
4 8
7 9 8 9


Sample output:
5

Submission status: Runtime Error

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
x = [0] + x
dp = [[[0 for _ in range(max(x)*n+1)] for _ in range(n+1)] for _ in range(n+1)]
x.sort()
for j in range(n+1):
    for k in range(n+1):
        for s in range(max(x)*n+1):
            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif j >= 1 and s < x[j]:
                dp[j][k][s] = dp[j-1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j]]
            else:
                dp[j][k][s] = 0

ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]

print(ans)

Submission status: Runtime Error

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
max_x = max(x)
dp = [[[0]*(n*max_x+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 1
for i in range(n+1):
  for j in range(n+1):
    for k in range(n*max_x+1):
      if i>=1 and k < x[i-1]:
        dp[i][j][k] = dp[i-1][j][k]
      elif i>=1 and j>= 1 and k>= x[i-1]:
        dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
      else:
        continue
ans = 0
for j in range(1,n+1):
  ans += dp[n][j][j*a]
print(ans)

Submission status: Runtime Error

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
t = [[0]*5001 for _ in range(n+1)]
ans = 0
for i in range(1, n+1):
  for y in x:
    for z in t[i-1]:
      t[i][z+y-a] += 1
  ans += t[i][0]
print(ans)

Submission status: Runtime Error

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
t = [[0]*5001 for _ in range(n+1)]
ans = 0
for i in range(1, n+1):
  for y in x:
    for z in t[i-1]:
      t[z+y-a] += 1
  ans += t[i][0]
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1LL << 60;
int MOD = 1000000007;
double PI = 3.14159265358979323846;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define For(i,s,n) for (int i=s;i<(int)(n);i++)
#define vi vector<int>
#define vii vector< vector<int> >
#define All(c) (c).begin(), (c).end()
#define Print(x) cout<<(x)<<"\n"

int N, A;
int X[51];
ll dp[51][51][2501];

int main() {
	cin >> N >> A;
	rep(i, N) cin >> X[i];


	rep(i, 51) {
		rep(j, 51) {
			rep(k, 2501) {
				if (i == 0 && j == 0 && k == 0) {
					dp[i][j][k] = 1;
				}
				else if (i>=1 && k<X[i-1]) {
					dp[i][j][k] = dp[i - 1][j][k];
				}
				else if (i>=1 && j>=1 && k>=X[i-1]){
					dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - X[i-1]];
				}
			}
		}
	}

	ll ans = 0;
	rep1(i, N+1) {
		ans += dp[N][i][i * A];
	}
	cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
def resolve():
    N, A = list(map(int, input().split()))
    X = sorted(list(map(int, input().split())))
    cnt = 0
    for bits in range(1, 1<<N):
        flags = list(bin(bits)[2:].zfill(N))
        _X = [x for i, x in enumerate(X) if flags[i]=="1"]
        cnt += 1 if sum(_X)/len(_X) == A 
    print(cnt)
    


if '__main__' == __name__:
    resolve()

Submission status: Runtime Error

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
t=[[[0]*(n*a+1)]*(n+1)]*(n+1)
ans=0
for j in range(n+1):
  for k in range(n+1):
    if k>j:
      break
    for s in range((n+1)*a+1):
      if s==0 and k==0 and j==0:
        t[j][k][s]=1
      elif j>=1 and x[j-1]>s:
        t[j][k][s]=t[j-1][k][s]
      elif j>=1 and k>=1 and x[j-1]<=s:
        t[j][k][s]=t[j-1][k][s]+t[j-1][k-1][s-x[j-1]]
      if j==n and k>=1 and s==k*a:
        ans+=t[j][k][s]
print(ans)

Submission status: Runtime Error

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
t=[[[0 for s in range(k*a+1)]for k in range(j+1)]for j in range(n+1)]
for j in range(n+1):
  for k in range(j+1):
    for s in range(k*a+1):
      if s==0 and k==0 and j==0:
        t[j][k][s]=0
      elif j>=1 and x[j+1]<s:
        t[j][k][s]=t[j-1][k][s]
      elif j>=1 and k>=1 and x[j+1]>=s:
        t[j][k][s]=t[j-1][k][s]+t[j-1][k-1][s-x[j+1]]
ans=0
for i in range(n):
  ans+=t[n][i+1][(i+1)*a]
print(ans)

Submission status: Runtime Error

Solution code:
n, a = [int(i) for i in input().split()]
x = [int(i)-a for i in input().split()] 

max = max(x)

dp = [[0 for _ in range(2*n*max+1)] for _ in range(n+1)]

dp[0][n*max] = 1 

for i in range(1, n+1):
	for j in range(2*n*max+1):
		if j - x[i-1] < 0 or j - x[i-1] > 2*n*max:
			dp[i][j] = dp[i-1][j]
		else: 
			dp[i][j] = dp[i-1][j] + dp[i-1][j-x[i-1]]

print(dp[n][n*max]-1)

Submission status: Runtime Error

Solution code:
n, a = [int(i) for i in input().split()]
x = [int(i)-a for i in input().split()] 

max = max(x)

dp = [[0 for _ in range(2*n*max+1)] for _ in range(n+1)]

dp[0][n*max] = 1 

for i in range(1, n+1):
	for j in range(2*n*max+1):
		if j - x[i-1] < 0 or j - x[i-1] > 2*n*max:
			dp[i][j] = dp[i-1][j]
		else: 
			dp[i][j] = dp[i-1][j] + dp[i-1][j-x[i-1]]

print(dp[n][n*max]-1)







# # def function(i, j, x):
# 	print(0)
# 	if i == 0 and j == 0:
# 		return 1
# 	elif i == 0 and j == x[0]:
# 		return 1
# 	else:
# 		return function(i-1, j, x) + function(i-1, j-x[i], x)

Submission status: Runtime Error

Solution code:
n, a = [int(i) for i in input().split()]
x = [int(i)-a for i in input().split()] 

max = max(x)

dp = [[0 for _ in range(2*n*max)] for _ in range(n)]

dp[0][n*max+x[0]] = 1
dp[0][n*max] = 1 

for i in range(1, n):
	for j in range(2*n*max):
		if j - x[i] < 0 or j - x[i] >= 2*n*max:
			dp[i][j] = dp[i-1][j]
		else: 
			dp[i][j] = dp[i-1][j] + dp[i-1][j-x[i]]

print(dp[n-1][n*max]-1)







# # def function(i, j, x):
# 	print(0)
# 	if i == 0 and j == 0:
# 		return 1
# 	elif i == 0 and j == x[0]:
# 		return 1
# 	else:
# 		return function(i-1, j, x) + function(i-1, j-x[i], x)

Submission status: Runtime Error

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N,A=imn()
x = iln()
X = max(x)

dp = [[[0 for _ in range(N*X+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for j in range(N):
    for k in range(N):
        for s in range(N*X+1):
            #dp[j+1][k][s] = max(dp[j+1][k][s], dp[j][k][s])
            if s-x[j] < 0:
                dp[j+1][k][s] = dp[j][k][s]
            else:
            #if s-x[j] >= 0:
                dp[j+1][k+1][s] = dp[j][k+1][s] + dp[j][k][s-x[j]]


ans = 0
for i in range(1, N+1):
    ans += dp[N][i][i*A]
    #print(dp[i][1])
    #print(dp[N][i][i*A])
print(ans)

Submission status: Runtime Error

Solution code:
def resolve():
	modu = 1000000007
	n, m = map(int, input().split())
	a = [False]*n
	for _ in range(m):
		a[int(input())] = True
	dp = [0]*(n+1)
	dp[0], dp[1] = 1, 1
	for i in range(2, n+1):
		if a[i]:
			continue
		multi = []
		if not a[i-1]:
			multi.append(dp[i-1])
		if not a[i-2]:
			multi.append(dp[i-2])
		dp[i] = sum(multi) % modu
	print(dp[-1])
resolve()

Submission status: Runtime Error

Solution code:

import math

def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)

N, A = list(map(int, input().split()))
X = sorted(list(map(int, input().split())))
numbers = [0 for i in range((N*A)+1)]
for each in X:
    numbers[each] += 1
g = numbers.copy()
def ways(a, k, arr, g):
    global numbers
    f = g.copy()
    if a == 0 and k == 0:
        # print(each)
        n = 1
        # print(arr)
        
        for each in set(arr):
            n *= int(nCr(numbers[each],arr.count(each)))
        return n
    if a == 0 and k != 0:
        return 0
    if k == 0 and a != 0:
        return 0
    nways = 0
    for i in range(a, 0, -1):
        # print('i', i, numbers[i])
        if f[i] > 0:
            f[i] -= 1
            nways += ways(a-i, k-1, arr+[i], f)
            f[i] = 0
        # print(numbers)
    return nways

w = 0
for a in range(A, (N*A)+A, A):
    numbers = g.copy()
    w += ways(a, int(a/A), [], numbers)
    # print('w', w)
print(w)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

n, a, *x = map(int, sys.stdin.read().split())

def main():
    m = max(n, a) * max(x)
    dp = np.zeros((n + 1, m + 1), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(n):
        ndp = np.copy(dp)
        for j in range(1, n + 1):
            ndp[j][x[i]:] += dp[j-1][:m-x[i]+1]
        dp = ndp
    i = np.arange(1, n + 1)
    print(np.sum(dp[i, i * a]))

if __name__ ==  '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
from functools import lru_cache, reduce
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# ここから書き始める
n, a = map(int, input().split())
x = list(map(int, input().split()))
if n == 1:
    if x[0] == a:
        print(1)
    else:
        print(0)
else:
for i in range(n):
    x[i] -= a
# x.sort()
dp = [[0 for j in range(99)] for i in range(n)]
# print(dp)
for i in range(n):
    if i == 0:
        dp[i][49] = 1
        dp[i][x[i] + 49] += 1
        continue
    for j in range(99):
        dp[i][j] = dp[i - 1][j]
        if 0 <= j - x[i] <= 98:     
            dp[i][j] += dp[i - 1][j - x[i]]
ans = dp[-1][49]
# for i in range(n):
    # print(dp[i])
print(ans - 1)

Submission status: Runtime Error

Solution code:
import math
import collections

def comb(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

n,a = map(int,input().split())

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

memo = [0]*51

for i in t:
    memo[i] += 1

typecount = []

ans = 0

for i in t:
    if i != a:
        typecount.append(i)

for i in range(1,len(typecount)):
    for j in itertools.combinations(typecount,i):
        if int((sum(j)/len(j))*100) == int(sum(j)/len(j))*100:
            if int(sum(j)/len(j))==a:
                #print(j)
                ans += 2**(memo[a])
            

if 0 < memo[a]:
    for i in range(1,memo[a]+1):
        ans += comb(memo[a], i)

print(ans)

Submission status: Runtime Error

Solution code:
import math
def combination(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

import collections

n,a = map(int,input().split())

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

memo = [0]*51

for i in t:
    memo[i] += 1

typecount = []

ans = 0

for i in t:
    if i != a:
        typecount.append(i)

for i in range(1,len(typecount)):
    for j in itertools.combinations(typecount,i):
        if int((sum(j)/len(j))*100) == int(sum(j)/len(j))*100:
            if int(sum(j)/len(j))==a:
                #print(j)
                ans += 2**(memo[a])
            

if 0 < memo[a]:
    for i in range(1,memo[a]+1):
        ans += combination(memo[a], i)

print(ans)

Submission status: Runtime Error

Solution code:
import math
def combination(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

import collections

n,a = map(int,input().split())

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

memo = [0]*51

for i in t:
    memo[i] += 1

typecount = []

ans = 0

for i in t:
    if i != a:
        typecount.append(i)

for i in range(1,len(typecount)):
    for j in itertools.combinations(typecount,i):
        if int((sum(j)/len(j))*10) == int(sum(j)/len(j))*10:
            if int(sum(j)/len(j))==a:
                #print(j)
                ans += 2**(memo[a])
            

if 0 < memo[a]:
    for i in range(1,memo[a]+1):
        ans += combination(memo[a], i)

print(ans)

Submission status: Runtime Error

Solution code:
import math
def combination(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

import collections

n,a = map(int,input().split())

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

memo = [0]*51

for i in t:
    memo[i] += 1

typecount = []

ans = 0

for i in t:
    if i != a:
        typecount.append(i)

for i in range(1,len(typecount)):
    for j in itertools.combinations(typecount,i):
        if sum(j)/len(j)==a:
            ans += 2**(memo[a])
            

if 0 < memo[a]:
    for i in range(1,memo[a]+1):
        ans += combination(memo[a], i)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,a = map(int,readline().split())
lst1 = list(map(int,readline().split()))

import numpy as np

dp = np.zeros((n+1,3000),dtype=np.int64) # 枚数、目標数ごとに場合の数
dp[0,0] = 1

for x in lst1:
  dp[1:,x:] += dp[:-1,:-x].copy()
  
ans = 0
for i in range(1,n+1):
  ans += dp[i,i*lst1]
  
print(ans)

Submission status: Runtime Error

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

result=0
lists=[]

import numpy as np


for i in range(2**N):
    list2 =[]
    for j in range(N):
        if (i >> j) &1 == 1:
            list2.append(cards[j])
            lists.append(list2)

lists=np.array(lists)
unique_array = np.unique(lists)
lists=unique_array.tolist()

for j in range(len(lists)):
    ave = sum(lists[j])/len(lists[j])
    if ave ==A:
        result+=1

print(result)

Submission status: Runtime Error

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

result=0
lists=[]

import numpy as np


for i in range(2**N):
    list2 =[]
    for j in range(N):
        if (i >> j) &1 == 1:
            list2.append(cards[j])
            lists.append(list2)

lists=np.array(lists)
unique_array = np.unique(lists)
lists=unique_array.tolist()
print(lists)

for j in range(len(lists)):
    ave = sum(lists[j])/len(lists[j])
    if ave ==A:
        result+=1

print(result)

Submission status: Runtime Error

Solution code:
N, A = map(int, input().split())
a = list(map(int, input().split()))
X = max(a)
ans = 0
dp = [[[0 for i in range(N*X+1)]for j in range(N+1)]for k in range(N+1)]
dp[0][0][0] = 1

for j in range(N):
    for k in range(N+1):
        for s in range(N*X+1):
            if a[j]>s:
                dp[j+1][k][s] = dp[j][k][s]
            elif a[j]<=s and 1<=k:
                dp[j+1][k][s] = dp[j][k][s] + dp[j][k-1][s-a[j]]

for k in range(1,N+1):
    ans += dp[N][k][k*A]

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

N, A = map(int, input().split())
a = [0]+list(map(int, input().split()))
X = max(a)
dp = [[[0 for i in range(N*X+1)] for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 1
for i in range(N+1):
    for j in range(N+1):
        for k in range(N*X+1):
            if i>=1 and k<a[i]:
                dp[i][j][k]=dp[i-1][j][k]
            elif i>=1 and j>=1 and k>=a[i]:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-a[i]]
ans = 0
for j in range(1,N+1):
    ans += dp[N][j][j*A]
print(ans)

Submission status: Runtime Error

Solution code:
N, A = map(int, input().split())
a = [0]+list(map(int, input().split()))
X = max(a)
dp = [[[0 for i in range(N*X+1)] for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 1
for i in range(N+1):
    for j in range(N+1):
        for k in range(N*X+1):
            if i>=1 and k<a[i]:
                dp[i][j][k]=dp[i-1][j][k]
            elif i>=1 and j>=1 and k>=a[i]:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-a[i]]
ans = 0
for j in range(1,N+1):
    ans += dp[N][j][j*A]
print(ans)

Submission status: Runtime Error

Solution code:
N, A = map(int, input().split())
a = [0]+list(map(int, input().split()))
X = max(a)
dp = [[[0 for i in range(N*X+1)] for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 1

for i in range(N+1):
    for j in range(N+1):
        for k in range(N*X+1):
            if i>=1 and k<a[i]:
                dp[i][j][k]=dp[i-1][j][k]
            elif i>=1 and j>=1 and k>=a[i]:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-a[i]]

ans = 0
for j in range(1,N+1):
    ans += dp[N][j][j*A]
print(ans)

Submission status: Runtime Error

Solution code:
N, A = map(int, input().split())
a = [0]+list(map(int, input().split()))
X = max(a)
dp = [[[0 for i in range(N*X+1)] for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 1

for i in range(N+1):
    for j in range(N+1):
        for k in range(N*X+1):
            if i>=1 and k<a[i]:
                dp[i][j][k]=dp[i-1][j][k]
            elif i>=1 and j>=1 and k>=a[i]:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-a[i]]

ans = 0
for j in range(1,N+1):
    ans += dp[N][j][j*A]
print(ans)

Submission status: Runtime Error

Solution code:
N,A=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0]*(N*N+100) for j in range(N+10)] for i in range(N+10)]
dp[0][0][0]=1
for i in range(N):
    for j in range(N+1):
        for k in range(sum(x)+1):
            if(dp[i][j][k]!=0):
                dp[i+1][j][k]+=dp[i][j][k]
                dp[i+1][j+1][k+x[i]]+=dp[i][j][k]
print(sum(dp[N][i][i*A] for i in range(1,N+1)))

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc044/tasks/arc060_a
# ソートしてからごちゃごちゃやればどうにかなりそう(無理でした)

'''
解説満点解法1
もしもk枚選んだとき、合計がsになる通りの数がわかったら？→s=k*Aとなる場合の数の合計をすれば良い

k枚選んだとき、合計がsになる通りの数は典型的なDP！
dp(j,k,s)... X[0:j]からk枚選んで、その合計をsにするような選び方の総数
と定義すると、
dp(j+1,k,s) = X[j]を選んだ結果sになったときの通りの数 + X[j]を選ばずにsになっている通りの数 なので
dp(j+1,k,s) = dp(j,k-1,s-X[j]) + dp(j,k,s)

あとは初期条件と境界条件と伝播条件を付け加える。
境界条件 dp(j,k,0)=0 (数枚選んで合計が0になるのはありえない)
初期条件 dp(j,0,0)=1 (ただし、0枚選んだときは1通りとなる)(s-X[j]=0のときに1通りとなってほしいという気持ちもある)

伝播条件 s-X[j]<0に関しては dp(j-1,k-1,s-X[j])が必ず0通りとなる(ありえないので)
'''

import sys
read = sys.stdin.readline
from itertools import product


def read_ints():
    return list(map(int, read().split()))


N, A = read_ints()
X = read_ints()
S = sum(X)

# 満点解法1
dp = [[[0] * (S + 1) for _ in range(N + 1)] for _ in range(N + 1)]
for j in range(N + 1):  # 初期条件
    dp[j][0][0] = 1  # 1枚も選ばずに0になるのは1通り


for j, k, s in product(range(N), range(1, N + 1), range(S + 1)):
    dp[j + 1][k][s] = dp[j][k][s] + \
        (0 if s - X[j] < 0 else dp[j][k - 1][s - X[j]])

# s=k*Aとなるような通りの数の総数
ans = 0
for k in range(1, N + 1):  # 0個はとる通りの数はいらない
    ans += dp[N][k][k * A]

# print(dp)
print(ans)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc044/tasks/arc060_a
# ソートしてからごちゃごちゃやればどうにかなりそう(無理でした)

'''
解説満点解法1
もしもk枚選んだとき、合計がsになる通りの数がわかったら？→s=k*Aとなる場合の数の合計をすれば良い

k枚選んだとき、合計がsになる通りの数は典型的なDP！
dp(j,k,s)... X[0:j]からk枚選んで、その合計をsにするような選び方の総数
と定義すると、
dp(j+1,k,s) = X[j]を選んだ結果sになったときの通りの数 + X[j]を選ばずにsになっている通りの数 なので
dp(j+1,k,s) = dp(j,k-1,s-X[j]) + dp(j,k,s)

あとは初期条件と境界条件と伝播条件を付け加える。
境界条件 dp(j,k,0)=0 (数枚選んで合計が0になるのはありえない)
初期条件 dp(j,0,0)=1 (ただし、0枚選んだときは1通りとなる)(s-X[j]=0のときに1通りとなってほしいという気持ちもある)

伝播条件 s-X[j]<0に関しては dp(j-1,k-1,s-X[j])が必ず0通りとなる(ありえないので)
'''

import sys
read = sys.stdin.readline
from itertools import product


def read_ints():
    return list(map(int, read().split()))


N, A = read_ints()
X = read_ints()
S = sum(X)

# 満点解法1
dp = [[[0] * (S + 1) for _ in range(N + 1)] for _ in range(N + 1)]
for j in range(N + 1):  # 初期条件
    dp[j][0][0] = 1  # 1枚も選ばずに0になるのは1通り


for j, k, s in product(range(N), range(1, N + 1), range(S + 1)):
    dp[j + 1][k][s] = dp[j][k][s] + \
        (0 if s - X[j] < 0 else dp[j][k - 1][s - X[j]])

# s=k*Aとなるような通りの数の総数
ans = 0
for k in range(1, N + 1):  # 0個はとる通りの数はいらない
    ans += dp[N][k][k * A]

# print(dp)
print(ans)


'''
満点解法2


'''

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n,a=map(int,input().split())
x=[0]+list(map(int,input().split()))
su=sum(x)
maxi=max(x)
dp=[[[0 for k in range(su+1)] for j in range(51)] for i in range(51)]
dp[0][0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(maxi*j+1):
            if k<x[i]:
                dp[i][j][k]=dp[i-1][j][k]
            if k>=x[i] and j>=1:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-x[i]]
ans=0
for t in range(1,n+1):
    if a*t<=su:
        ans+=dp[n][t][a*t]
    else:
        break
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,A=MI()
    x=LI()
    M=max(x)
    
    #dp[i][j][k]はi番目まで，j枚で，和がkにできるか
    dp=[[[0]*(N*M+1) for j in range(N+1)] for _ in range(N+1)]
    dp[0][0][0]=1
    
    for i in range(N):
        for j in range(i+1):
            for k in range(N*M+1-x[i]):
                if dp[i][j][k]:
                    dp[i+1][j][k]+=dp[i][j][k]
                    dp[i+1][j+1][k+x[i]]+=dp[i][j][k]
                    

        
    ans=0
    for j in range(1,N+1):        
        ans+=dp[-1][j][j*A]
        
    print(ans)
 

            

main()

Submission status: Runtime Error

Solution code:
N, A = map(int, input().split())
x = [0] + [int(i) for i in input().split()]

dp = [[[0]*(N*max(x)+1)]*(N+1) for _ in range(N+1)]
dp[0][0][0] = 1

for i in range(N+1):
    for j in range(N+1) :
        for k in range(N*max(x)+1) :
            if i >= 1 and k < x[i] :
                dp[i][j][k] = dp[i-1][j][k]
            if i >= 1 and j >= 1 and k >= x[i] :
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-x[i]]

ans = 0
for j in range(N+1) :
    ans += dp[N][j][j*A]
print(ans-1)

Submission status: Runtime Error

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7

N, A = MI()
X = LMI()

# dp[i][j][s] := i番目までのカードからj枚を選んで合計がsになる組み合わせの数
dp = [[[0] * (A * N + 1) for _ in range(N + 1)] for _ in range(N)]
for i in range(N):
    dp[i][0][0] = 1
dp[0][1][X[0]] = 1
for i in range(1, N):
    for j in range(1, i + 2):
        for s in range(A * N + 1):
            if s - X[i] < 0:
                dp[i][j][s] = dp[i - 1][j][s]
            else:
                dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - X[i]]

ans = 0
for i in range(1, N + 1):
    ans += dp[N - 1][i][A * i]
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7

N, A = MI()
X = LMI()
mx = max(X)

# dp[i][j][s] := i番目までのカードからj枚を選んで合計がsになる組み合わせの数
dp = [[[0] * (N * mx + 1) for _ in range(N + 1)] for _ in range(N)]
for i in range(N):
    dp[i][0][0] = 1
dp[0][1][X[0]] = 1
for i in range(N):
    for j in range(1, i + 2):
        for s in range(N * mx + 1):
            dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - X[i]]

ans = 0
for i in range(1, N + 1):
    ans += dp[N - 1][i][A * i]
print(ans)

Submission status: Runtime Error

Solution code:
N, A = map(int, input().split())
x = list(map(int, input().split()))
MAX_J = sum(x)
dp = [[0] * (MAX_J+1) for i in range(N+1)]
dp[0][0] = 1
for n in range(N):
    for i in range(N)[::-1]:
        for j in range(MAX_J-x[n]+1)[::-1]:
            dp[i+1][j+x[n]] += dp[i][j]
ans = 0
for i in range(1, N+1):
    ans += dp[i][A * i]
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N, A = map(int,input().split())
x = np.array(list(map(int,input().split())))
x_diff = np.sort(x - A)
posi_list = []
posi = 0
for posi_i in x_diff[x_diff>0]:
    posi_list.append(posi_i)
    posi += posi_i
    posi_list.append(posi)
    
nega_list = []
nega = 0
for nega_i in x_diff[x_diff<0]:
    nega_list.append(nega_i)
    nega += nega_i
    nega_list.append(nega)
    
posi_list.pop(0)
nega_list.pop(0)

posi_nega = 0
posi_new = []
nega_new = []
for posi in posi_list:
    for nega in nega_list:
        if posi+nega==0:
            posi_nega += 1
            posi_new.append(posi)
            nega_new.append(nega)
            
zeros = len(x_diff[x_diff==0])
posi_nega = zeros+posi_nega*2
print(posi_nega)

Submission status: Runtime Error

Solution code:
import itertools

n, a = map(int, input().split())
cards = list(map(int, input().split()))
combi = []
for i in range(2, len(cards) + 1):
  cm = []
  c = itertools.combinations(cards, i)
  for i in range(len(c)):
    if min(c[i]) <= a:
      cm += c
  combi += cm
r = 0
for i in range(len(cards)):
    if cards[i] == a:
        r += 1
for i in range(len(combi)):
  if sum(combi[i]) / len(combi[i]) == a:
    r += 1
print(r)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int, A: int, x: "List[int]"):
    ## dp[i][j][k] = i番目までのカードからjマイ選んで合計kにする選び方の総数
    dp = [[[0]*2500 for _ in range(N+1)] for _ in range(N+1)]

    for i in range(N):
        dp[i][0][0] = 1

    for i in range(N):
        for j in range(N):
            for k in range(2500):
                if k-x[i] >= 0:
                    dp[i+1][j+1][k] = dp[i][j][k-x[i]]+dp[i][j+1][k]
                else:
                    dp[i+1][j+1][k] = dp[i][j+1][k]

    answer = 0
    for j in range(1,N+1):
        answer += dp[N][j][A*j]
    print(answer)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    x = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, x)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

# 2 ** 50 -> 全探索は厳しい -> DP
# dp[i][k][wa] = i枚まで見て、k枚選んだ時の合計値がwaとなるときの選び方の合計
# max wa = max(X) * N
max_wa = max(X) * N
dp = [[[0] * (max(X) * (N+1)) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for k in range(i+1):
        for wa in range(max_wa):
            # 選ぶとき
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            # 選ばないとき
            dp[i+1][k][wa] += dp[i][k][wa]

ans = 0
for k in range(1, N+1):
    ans += dp[-1][k][k*A]

print(ans)