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: Time Limit Exceeded

Solution code:
b = []
def binomial(n):
    global b
    b = [None] * n
    for i in range(n):
        b[i] = [0] * n
        b[i][i] = 1
    for i in range(1, n):
        for j in range(1, i + 1):
            b[i][j] = b[i - 1][j - 1] + b[i - 1][j]
    
cache = {}

def s(x, a, k, i):
    if a < 0: return 0
    if k < 0: return 0
    if k == 0:
        if a == 0: return 1
        else: return 0
    if i > a: return 0
    if i == 51: return 0
    key = (a, k, i)
    if key in cache: return cache[key]
    c = s(x, a, k, i + 1)
    for j in range(1, x[i] + 1):
        c += b[x[i] + 1][j + 1] * s(x, a - i * j, k - j, i + 1)
    cache[key] = c
    return c

n, a = map(int, input().split())
binomial(n + 2)
x = [0] * 51
for k in input().split():
    x[int(k)] += 1

c = 0
for i in range(1, n + 1):
    c += s(x, a * i, i, 0)
print(c)

Submission status: Time Limit Exceeded

Solution code:
b = []
def binomial(n):
    global b
    b = [None] * n
    for i in range(n):
        b[i] = [0] * n
        b[i][i] = 1
    for i in range(1, n):
        for j in range(1, i + 1):
            b[i][j] = b[i - 1][j - 1] + b[i - 1][j]
    
cache = {}

def s(x, a, k, i):
    key = (a, k, i)
    if key in cache: return cache[key]
    if a < 0: return 0
    if k < 0: return 0
    if k == 0:
        if a == 0: return 1
        else: return 0
    if i > a: return 0
    if i == 51: return 0
    c = s(x, a, k, i + 1)
    for j in range(1, x[i] + 1):
        c += b[x[i] + 1][j + 1] * s(x, a - i * j, k - j, i + 1)
    cache[key] = c
    return c

n, a = map(int, input().split())
binomial(n + 2)
x = [0] * 51
for k in input().split():
    x[int(k)] += 1

c = 0
for i in range(1, n + 1):
    c += s(x, a * i, i, 0)
print(c)

Submission status: Time Limit Exceeded

Solution code:
def factorial(n):
    k = 1
    for i in range(n): k *= (i + 1)
    return k

def binomial(a, b):
    return factorial(a) // (factorial(a - b) * factorial(b))

cache = {}

def s(x, a, k, i):
    key = (a, k, i)
    if key in cache: return cache[key]
    if a < 0: return 0
    if k < 0: return 0
    if k == 0:
        if a == 0: return 1
        else: return 0
    if i > a: return 0
    if i == 51: return 0
    c = s(x, a, k, i + 1)
    for j in range(1, x[i] + 1):
        c += binomial(x[i], j) * s(x, a - i * j, k - j, i + 1)
    cache[key] = c
    return c

n, a = map(int, input().split())
x = [0] * 51
for k in input().split():
    x[int(k)] += 1

c = 0
for i in range(1, n + 1):
    c += s(x, a * i, i, 0)
print(c)

Submission status: Time Limit Exceeded

Solution code:
n,a = (int(i) for i in input().split())
x = [int(i) for i in input().split()]
m,answer = max(max(x),a),0
dp = [[[0]*(n*m+1) for i in range(n+1)] for i 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*m+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]]
for j in range(1,n+1):
	answer += dp[n][j][j*a]
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
print(solve(N,A,X))

Submission status: Time Limit Exceeded

Solution code:
def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for i in range(N+1)] for j in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.append(0)
X.sort()
ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0] * (ma+1) for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  cnt=X[i]
  for j in range(1,N+1):
    for k in range(ma+1):
      if k < cnt:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  if x*A<=ma:
    ans+=dp[N][x][x*A]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.insert(0,0)
ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0] * (ma+1) for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  cnt=X[i]
  for j in range(1,N+1):
    for k in range(ma+1):
      if k < cnt:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  if x*A<=ma:
    ans+=dp[N][x][x*A]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.append(0)
X.sort()
ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0 for i in range(ma+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  cnt=X[i]
  for j in range(1,N+1):
    for k in range(ma+1):
      if k < cnt:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  if x*A<=ma:
    ans+=dp[N][x][x*A]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.insert(0,0)
ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0 for i in range(ma+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  cnt=X[i]
  for j in range(1,N+1):
    for k in range(ma+1):
      if k < cnt:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  if x*A<=ma:
    ans+=dp[N][x][x*A]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.insert(0,0)
ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0 for i in range(ma+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(ma+1):
      if k < X[i]:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-X[i]]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  if x*A<=ma:
    ans+=dp[N][x][x*A]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.insert(0,0)
ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0 for i in range(N*50+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(ma+1):
      if k < X[i]:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-X[i]]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  if x*A<=ma:
    ans+=dp[N][x][x*A]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.insert(0,0)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0 for i in range(N*50+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(N*50+1):
      if k < X[i]:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-X[i]]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  ans+=dp[N][x][x*A]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

if __name__ == '__main__':
    n, average = list(map(int, input().split()))
    numbers = list(map(int, input().split()))

    count = 0
    for i in range(1, n+1):
        count += len(list(filter(lambda x: sum(x) == i * average, combinations(numbers, i))))
    print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-      
import numpy as np
n, a = list(map(int,input().split()))
x = list(map(int,input().split()))
max_x = max(x)
X = max(max_x,a)
dp = np.zeros((n+1,n+1,(n+1)*X)).tolist()

dp[0][0][0] = 1
for j in range(1,n+1):
    for k in range(0,n+1):
        for s in range(0,(n+1)*X):
            if(j>=1 and s<x[j-1]):
                dp[j][k][s] = dp[j-1][k][s]
            elif(j>=1 and k>=1 and s>=x[j-1]):
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]

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

Submission status: Time Limit Exceeded

Solution code:
N,A=map(int,raw_input().split())
x=[0]+map(int,raw_input().split())
#print x

max_n=max(x)

#dp=[[[0]*(max_n*N+1) for k in range(N+1)] for j in range(N+1)]
dp=[[[0]*3000 for k in range(51)] for j in range(51)]
#print dp


for j in range(N+1):
	for k in range(N+1):
		for s in range(max_n*N+1):
			if j==k==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
#print dp


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

print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections
import math
N,A=map(int,raw_input().split())
#print N,A
x=collections.Counter(map(int,raw_input().split()))
#print x

iv=[i for i in x.keys()]	#Item value
ic=[]	#Item count
for i in x.items():
	tmp=[i for i in range(i[1]+1)]
	ic.append(tmp)


ic_n=[len(_)-1 for _ in ic]

p=list(itertools.product(*ic))
#print "# p"
#print p		#Pattern

a=[]
for m in p:
	t_sum=0
	for j,k in zip(m,iv):
		t_sum+=j*k
	#print t_sum,len(m)
	if sum(m)!=0 and t_sum/sum(m)==A and t_sum%sum(m)==0 and sum(m)!=0:
		#print m,iv,t_sum,sum(m)
		a.append(m)

#print "# a"
#print a

def combination(n,r):
	g=[math.factorial(i) for i in range(100) ]
	return int(g[n]/(g[r]*g[n-r]))

ans=0
for i in a:
	t_cnt=1
	for j,k in zip(i,ic_n):
		if j!=0 or j!=k:
			t_cnt*= combination(k,j)
			pass
	#print t_cnt
	ans+=t_cnt
print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections
N,A=map(int,raw_input().split())
#print N,A
x=collections.Counter(map(int,raw_input().split()))
#print x

iv=[i for i in x.keys()]	#Item value
#print "# iv"
#print iv
ic=[]	#Item count
for i in x.items():
	tmp=[i for i in range(i[1]+1)]
	ic.append(tmp)

#print "# ic"
#print ic

ic_n=[len(_)-1 for _ in ic]
#print "# ic_n"
#print ic_n

p=list(itertools.product(*ic))
#print "# p"
#print p		#Pattern

a=[]
for m in p:
	#print "##"
	#print m,iv
	t_sum=0
	for j,k in zip(m,iv):
		t_sum+=j*k
	#print t_sum,len(m)
	if sum(m)!=0 and t_sum/sum(m)==A and t_sum%sum(m)==0 and sum(m)!=0:
		#print m,iv,t_sum,sum(m)
		a.append(m)

#print "# a"
#print a
#print len(a)

ans=0
for i in a:
	#print "=="
	t_cnt=1
	for j,k in zip(i,ic_n):
		if j!=0 or j!=k:
			#print j,k,len(list(itertools.combinations(range(k),j))) 
			t_cnt*=len(list(itertools.combinations(range(k),j)))
	#print t_cnt
	ans+=t_cnt
print ans

Submission status: Time Limit Exceeded

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

n,a = map(int,raw_input().split())
x = map(int,raw_input().split())
ans = 0
for p in itertools.product([True, False], repeat = n):
    tmp = 0
    for i in range(n):
        tmp += x[i] if p[i] else 0
    average = 1.0*tmp/sum(p) if sum(p)>0 else 0 
    if(average == int(average) and average == a):
        ans += 1 
print (ans)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
x = [int(i) for i in input().split()]
 
lim = sum(x)
dp = [[0]*(lim + 1) for i in range(N + 1)]
 
dp[0][0] = 1
 
for i in range(N):
    for k in range(N, 0, -1):
        for v in range(lim, -1, -1):
            if v - x[i] < 0:
                break
            dp[k][v] += dp[k - 1][v - x[i]]
 
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
ans = 0

def dfs(idx, N, choice, tot):
    if idx == N:
        global ans
        if choice > 0 and choice*A == tot:
            ans += 1
        return

    dfs(idx + 1, N, choice + 1, tot + x[idx])
    dfs(idx + 1, N, choice, tot)

N, A = map(int, input().split())
x = [int(i) for i in input().split()]

dfs(0, N, 0, 0)

print(ans)

Submission status: Time Limit Exceeded

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

dp = [[0]*(50*N + 1) for i in range(N + 1)]

dp[0][0] = 1

for i in range(N):
    for k in range(N, 0, -1):
        for v in range(50*N, x[i] - 1, -1):
            dp[k][v] += dp[k - 1][v - x[i]]

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

def main():
    N,A = map(int,input().split())
    x = list(map(int,input().split()))
    sum = 0
    for _ in range(N): # 何枚使うか
        d = _ + 1
        MAX = 50 * d + 1
        dp = [[i for i in [0]*MAX] for __ in range(d+1)]
        dp[0][0] = 1
        for i in range(N): # 次にどのカードを選択するか
            for j in reversed(range(d)): # 今何枚選んだか
                for k in range(MAX): #現在の総和は？
                    if dp[j][k] == 0:
                        continue
                #カードiを選ぶ場合
                    if j + 1 <= d and k + x[i] <= d * A:
                        dp[j+1][k+x[i]] += dp[j][k]
                #カードiを選ばない場合
        sum += dp[d][d*A]
    print(sum)
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8;

def f(cards, tc):
    global ct, used, calculated, a
    cs = sum(tc)
    if cs == 0: return
    il = [i for i, x in enumerate(cards) if x > 0]

    if cs / len(il) == a and il not in used:
        used.append(il)
        calculated.append(set(tc))
        ct += 1

    for i, c in enumerate(cards):
        if c == 0: continue
        vc = cards[:]
        vc[i] = 0
        ic = vc[:]
        ic.pop(i)
        f(vc, ic)

def main(cards):
    f(cards, cards)
    print(ct)

if __name__ == '__main__':
    ct = 0
    used = []
    calculated = []
    n, a = map(int, input().split())
    cards = list(map(int, input().split()))
    main(cards)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import math
N, A = map(int,input().split())
x = [0] + list(map(int,input().split()))
ans = 0
if max(x) < A:
    maximum = A
else:
    maximum = max(x)
#sum/n = A ---> sum = nA
#calc[a][b][c] a番目のカードまで選んでからb枚を抜き出した時、合計がcになる通り。
calc = [[[0 for c in range(N*maximum+1)] for b in range(N+1)] for a in range(N+1)]
for a in range(N+1):
    for b in range(N+1):
        for c in range(N*maximum+1):
            if not a and not b and not c:
                calc[a][b][c] = 1
            elif a >= 1 and b >= 1 and c >= x[a]:
                calc[a][b][c] = calc[a-1][b][c]+calc[a-1][b-1][c-x[a]]
            elif a >= 1 and c < x[a]:
                calc[a][b][c] = calc[a-1][b][c]
            else:
                calc[a][b][c] = 0

for b in range(1,N+1):
    ans += calc[N][b][b*A]
print(ans)

Submission status: Time Limit Exceeded

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

import itertools
import numpy


def solve(n, a, xs0):
    xs = numpy.insert(xs0, 0, 0)
    xs.sort()
    y = max(xs.max(), a)
    dp = numpy.zeros((n + 1, n + 1, n * y + 1), numpy.int64)
    g = itertools.product(range(n + 1), range(n + 1), range(n * y + 1))
    for j, k, s in g:
        if j == k == s == 0:
            dp[j, k, s] = 1
        elif j >= 1 and s < xs[j]:
            dp[j, k, s] = dp[j - 1, k, s]
        elif j >= 1 and k >= 1 and s >= xs[j]:
            dp[j, k, s] = dp[j - 1, k, s] + dp[j - 1, k - 1, s - xs[j]]
    ans = sum(dp[n][k][k * a] for k in range(1, n + 1))
    return ans


def main():
    n, a = (int(x) for x in input().split())
    xs = numpy.fromiter((int(x) for x in input().split()), numpy.int64)
    ans = solve(n, a, xs)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
X = sorted(map(int, input().split()))
ans = 0
def f(l, i, b):
    global ans
    if len(l) > 0:
        s = sum(l)
        if s//len(l) == A and s%len(l) == 0 and b:
            ans += 1
            b = False
        if s//len(l) > A : return
    if i >= N : return
    f(l, i+1, False)
    f(l+[X[i]], i+1, True)
f([], 0, True)
print(ans)

Submission status: Time Limit Exceeded

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

dp = [[[0] * (n + 1) for i in range(n + 1)] for j in range(50 * 50 + 1)]
dp[0][0][0] = 1

for j in range(1, n + 1):
    for k in range(n + 1):
        for s in range(50 * 50 + 1):
            if s < x[j - 1]:
                dp[s][k][j] += dp[s][k][j - 1]
            else :
                dp[s][k][j] += dp[s][k][j - 1] + dp[s - x[j - 1]][k - 1][j - 1]

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, average = map(int, input().split())
lst = list(map(int, input().split()))
total = []

for i in range(1, len(lst) + 1):
    perm = list(itertools.combinations(lst, i))
    total.extend(perm)

count = 0
for i in total:
    avg = sum(i) / len(i)
    if avg == average:
        count += 1

print(count)

Submission status: Time Limit Exceeded

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

dp = [[[0 for i in range(n+1)] for j in range(n+1)] for k in range(50*n+1)]
count = 0

def dfs(i, j, sum):
    global count
    if dp[sum][j][i] != 0:
        return dp[sum][j][i]

    if i == n:
        if sum == a*j and j != 0:
            return 1
        else:
            return 0

    dp[sum][j][i] = dfs(i+1, j, sum) + dfs(i+1, j+1, sum + x[i])
    return dp[sum][j][i]

print(dfs(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N, A = map(int, input().split())
l = list(map(int, input().split()))
cnt = 0

for i in range(1,N+1):
	for cmb in combinations(l,i):
		if sum(cmb) / i == A:
			cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# !/usr/bin/env python
# vim: set fileencoding=utf-8 :

"""
#
# Author:   Noname
# URL:      https://github.com/pettan0818
# License:  MIT License
# Created: 火 11/ 8 17:04:53 2016

# Usage
#
"""

from itertools import repeat
from itertools import combinations
import sys

from statistics import mean

def read_input():
    first = input().split(" ")
    N = int(first[0])
    A = int(first[1])

    x_list = [int(i) for i in input().split(" ")]

    return N, A, x_list


def naive_checker(num_list, target_mean):
    """
    >>> naive_checker([7,9,8,9], 8)
    5
    >>> naive_checker([6,6,9], 8)
    0
    >>> naive_checker([3,6,2,8,7,6,5,9], 5)
    19
    >>> dns_child(0, 3, repeat(3,33))
    8589934591
    """
    ans = 0
    for i in range(1, len(num_list) + 1):
        for n in combinations(num_list, i):
            if mean(n) == target_mean:
                ans += 1
    print(ans)


if __name__ == '__main__':
    # import doctest
    # doctest.testmod()

    N, A, x_list = read_input()

    naive_checker(x_list, A)

Submission status: Time Limit Exceeded

Solution code:
N,A = map(int,raw_input().split(" "))
X = map(int,raw_input().split(" "))

# DP[50][50][50^2]
dp = [[[0 for k in range(50*N+1)] for k in range(N+1)]  for i in range(N+1)]
dp[0][0][0] = 1
for i in range(1,N+1):
    for j in range(N+1):
        for k in range(50*N+1):
            if k >= X[i-1] and j:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]  
            elif k < X[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
ans = 0
for j in range(1,N+1):
    ans +=  dp[N][j][j*A]
print ans

Submission status: Time Limit Exceeded

Solution code:
N,A = map(int,raw_input().split(" "))
X = map(int,raw_input().split(" "))
X.sort()
ans = 0
for c in range(1,N+1):
    n = c * A
    que = [(-1,0,0)]
    while que:
        index,q,s = que.pop(0)
        if (q == c and s == n):
            ans += 1

        for i in range(index+1,N):
            que.append((i,q+1,s+X[i]))

print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
NA = list(map(int,input().split(" ")))
xi = list(map(int,input().split(" ")))
counter = 0
for i in range(len(xi)):
    c = list(itertools.combinations(xi,i+1))
    for n in c:
        tmp = 0
        for t in range(len(n)):
            tmp = tmp + n[t]
        tmp = tmp / len(n)
        if tmp == float(NA[1]):
            counter = counter + 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:

def bits_list_sum(bits_value, value_list):
    sum = 0
    n = len(value_list)

    bin_bits = bin(bits_value)[2:].zfill(n)  

    for i in range(n):
        sum += int(bin_bits[n-1-i]) * value_list[i]

    return sum


#print(bits_list_sum(5, [1, 2, 3]) == 3)

select_ways = 0

N, A = input().split()
N = int(N)
A = int(A)
xn = input().split()
xn = list(map(int, xn))

for i in range(pow(2, N)):
    m =  bin(i)[2:].zfill(N).count('1')

    if bits_list_sum(i, xn) == m * A:
        select_ways += 1

print(select_ways-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, a = map(int, raw_input().split())
l = map(int, raw_input().split())
s = [i for i in range(len(l))]

ans = 0
for i in range(1, n + 1):
    combination = list(itertools.combinations(s, i))
    for j in combination:
        sum_temp = 0
        for index in j:
            sum_temp += l[index]
            
        if sum_temp == a * i:
            ans += 1

print ans

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
d = [x-A for x in list(map(int, input().split()))]
n = d.count(0)
d = [x for x in d if x != 0]
d.sort()
if not d:
	print(2**n - 1)
else:
	stack = []
	stack.append([0,0])
	stack.append([0,d[0]])
	ans = 0
	while stack:
		(pos, s) = stack.pop()

		if s == 0 and pos == len(d) - 1:
			ans += 1
		elif pos < len(d) - 1 and s <= 0:
			stack.append([pos+1,s])
			stack.append([pos+1,s + d[pos+1]])
	ans = ans * 2 ** n -1
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, A = [int(t) for t in input().split()]
x = [int(i) for i in input().split()]

K = max(x) * A
dp = np.zeros((51, 51, 2601))
dp[0, 0, 0] = 1

for i in range(N):
    for j in range(N):
        for k in range(sum(x)):
            if dp[i, j, k] == 0:
                continue
            dp[i+1, j+1, k+x[i]] += dp[i, j, k]
            dp[i+1, j, k] += dp[i, j, k]

print(int(sum(dp[N, j, j*A] for j in range(1, N+1))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, A = [int(t) for t in input().split()]
x = [int(i) for i in input().split()]

K = max(x) * A
dp = np.zeros((51, 51, 2601))
dp[0, 0, 0] = 1

for i in range(N):
    for j in range(N):
        for k in range(sum(x)):
            dp[i+1, j+1, k+x[i]] += dp[i, j, k]
            dp[i+1, j, k] += dp[i, j, k]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, A = [int(t) for t in input().split()]
x = [int(i) for i in input().split()]

K = max(x) * A
dp = np.zeros((51, 51, 2601))
dp[0, 0, 0] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, A = [int(t) for t in input().split()]
x = [int(i) for i in input().split()]

dp = np.zeros((51, 51, 2601))
dp[0, 0, 0] = 1

for i in range(N):
    for j in range(N):
        for k in range(2550):
            dp[i+1, j+1, k+x[i]] += dp[i, j, k]
            dp[i+1, j, k] += dp[i, j, k]

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

Submission status: Time Limit Exceeded

Solution code:
def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    n, a = reads()
    x = reads()
    s = sum(x)
    dp = [[[0]*3500 for j in range(n+1)] for i in range(n+1)]
    dp[0][0][0] = 1
    for i in range(n):
        for j in range(n):
            for k in range(s):
                dp[i][j+1][k] += dp[i][j][k]
                dp[i+1][j+1][k+x[j]] += dp[i][j][k]
    r = 0
    for j in range(1, n+1):
        r += dp[j][n][j*a]
    print(r)

main()

Submission status: Time Limit Exceeded

Solution code:
def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    n, a = reads()
    x = reads()
    s = sum(x)
    dp = [[[0]*(s+50) for j in range(n+1)] for i in range(n+1)]
    dp[0][0][0] = 1
    for i in range(n):
        for j in range(n):
            for k in range(s):
                dp[i][j+1][k] += dp[i][j][k]
                dp[i+1][j+1][k+x[j]] += dp[i][j][k]
    r = 0
    for j in range(1, n+1):
        r += dp[j][n][j*a]
    print(r)

main()

Submission status: Time Limit Exceeded

Solution code:
class nnTakAndCards:
	def count_pattern(self,N,A,x):
		bit = 1
		pattern = 0
		while bit < 1<<N:
			current_sum = 0
			for i in range(N):
				if bit & 1<<i:
					current_sum += x[i]-A
			if current_sum == 0:
				pattern += 1
			bit += 1
		print pattern

if __name__ == "__main__":
	N,A = map(int, raw_input().split())
	x = [int(i) for i in raw_input().split()]
	t = nnTakAndCards()
	t.count_pattern(N,A,x)

Submission status: Time Limit Exceeded

Solution code:
class nTakAndCards:
	def count_pattern(self,N,A,x):
		m = max(x)
		dp =[[[0 for k in range(N*A+10)] for j in range(N+1)] for i in range(N+1)]
		dp[0][0][0] = 1
		for i in range(N):
			for j in range(N):
				for k in range(N*A):
					if k+x[i]<=N*A:
						dp[i+1][j+1][k+x[i]] += dp[i][j][k]
					dp[i+1][j][k] += dp[i][j][k]
		ans = 0
		for j in range(1,N+1):
			ans += dp[N][j][j*A]
		print ans
					
if __name__ == "__main__":
	N,A = map(int, raw_input().split())
	x = [int(i) for i in raw_input().split()]
	t = nTakAndCards()
	t.count_pattern(N,A,x)

Submission status: Time Limit Exceeded

Solution code:
class TakAndCards:
	def count_pattern(self,N,A,x):
		bit = 1
		pattern = 0
		A = float(A)
		while bit < 1 << N:
			current_sum = 0.0
			b = 0.0
			for i in range(N):
				if bit & 1<<i:
					current_sum += x[i]
					b += 1.0
			if (current_sum/b) == A:
				pattern += 1
			bit += 1
		print pattern

if __name__ == "__main__":
	N,A = map(int, raw_input().split())
	x = [int(i) for i in raw_input().split()]
	t = TakAndCards()
	t.count_pattern(N,A,x)

Submission status: Time Limit Exceeded

Solution code:
N,A = map(int,input().split())
x = list(map(int,input().split()))
dp = [ [ [0]*2601 for i in range(51) ] for j in range(51) ]

X = max(x)
dp[0][0][0] = 1
for i in range(N):
    for j in range(i+1):
        for k in range(N*X-x[i]+1):
            dp[i+1][j+1][k+x[i]] += dp[i][j][k]
            dp[i+1][j][k] += dp[i][j][k]

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,A = map(int,input().split())
x = list(map(int,input().split()))
dp = [ [ [0]*3001 for i in range(51) ] for j in range(51) ]

X = max(x)
dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for k in range(N*X):
            dp[i+1][j+1][k+x[i]] += dp[i][j][k]
            dp[i+1][j][k] += dp[i][j][k]
          
ans = 0
for j in range(1,N+1):
    ans += dp[N][j][A*j]

print(ans)