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:
N,A = map(int, input().split())
x = list(map(int, input().split()))

ans = 0
for i in range(1,2**N):
    bit = i
    used = []
    for j in range(N):
        if bit & 1 == 1:
            used.append(True)
        else:
            used.append(False)
        bit = bit >> 1
    cnt = 0
    total = 0
    for j in range(len(used)):
        if used[j] == True:
            total += x[j]
            cnt += 1
    if total // cnt == A and total % cnt == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
kai,av=[int(x) for x in input().rstrip().split()]
l=[int(x) for x in input().rstrip().split()]
ll=[i for i in range(1,kai+1)]
result=[]
count=0


for i in ll:
    for j in itertools.combinations(l,r=i):
        if av==(sum(j)/i):
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
kai,av=[int(x) for x in input().rstrip().split()]
l=[int(x) for x in input().rstrip().split()]
ll=0
result=[]
count=0

for i in range(1,kai+1):
    for j in itertools.combinations(l,r=i):
        if av==(sum(j)/i):
            count+=1
print(count)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    a = A[i]
    for j in reversed(range(N)):
        for l in range(L+1):
            if l < a: continue
            dp[j+1][l] += dp[j][l-a]

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

M = sum(X)
dp = [[[0]*(N+1) for _ in range(M+1)] for _ in range(N+1)]
    
for i in range(N+1):
    dp[i][0][0] = 1
    
for i in range(N):
    for j in range(M+1):
        for k in range(1, N+1):
            if j >= X[i]:
                dp[i+1][j][k] = dp[i][j][k] + dp[i][j-X[i]][k-1]
            else:
                dp[i+1][j][k] = dp[i][j][k]
        
ans = 0
for k in range(1, N+1):
    if k*A <= M:
        ans += dp[N][k*A][k]
            
print(ans)

Submission status: Time Limit Exceeded

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

X = max(max(x), A)

dp = [[[0 for _ in range(N*X+1)] for _ in range(N+1)] for _ 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(N*X+1):
            if i >= 1 and k < x[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            elif i >= 1 and k >= 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:
                dp[i][j][k] = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,A = map(int, input().split())
  x = list(map(int, input().split()))
  count = 0
  for i in range(1,1 << len(x)):
      total = []
      for j in range(len(x)):
          if ((i >> j) & 1):
              total.append(x[j])
      if len(total):
          if (sum(total)/len(total)) == A:
              count += 1

  print(count)
  
main()

Submission status: Time Limit Exceeded

Solution code:
N,A = map(int, input().split())
x = list(map(int, input().split()))
count = 0
for i in range(1,1 << len(x)):
    total = []
    for j in range(len(x)):
        if ((i >> j) & 1):
            total.append(x[j])
    if len(total):
        if (sum(total)/len(total)) == A:
            count += 1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
N,A = map(int, input().split())
x = list(map(int, input().split()))
count = 0
for i in range(1 << len(x)):
    total = []
    for j in range(len(x)):
        if ((i >> j) & 1):
            total.append(x[j])
    if len(total):
        ave = sum(total)/len(total)
        if ave == A:
            count += 1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

count = 0
for i in range(1,n+1):
	li = list(itertools.combinations(x,i))
	for j in li:
		ave = sum(j) / len(j)
		if ave == a:
			count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

for i in range(n):
    x[i]-=a
    
left=x[:n//2]
l=len(left)
right=x[n//2:]
r=len(right)

data_left=Counter()
data_right=Counter()

for i in range(1,2**l):
    num=0
    for j in range(l):
        if (i>>j)&1==1:
            num+=left[j]
    data_left[-num]+=1

for i in range(1,2**r):
    num=0
    for j in range(r):
        if (i>>j)&1==1:
            num+=right[j]
    data_right[num]+=1

ans=data_left[0]+data_right[0]
for u,v in data_left.items():
    ans+=data_right[u]*v
    
print(ans)

Submission status: Time Limit Exceeded

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

ans=0

for i in range(1,2**n):
    count=0
    num=0
    for j in range(n):
        if (i>>j)&1==1:
            count+=1
            num+=x[j]
    if num%count==0 and num//count==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()]

sum_x = sum(x)

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

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

for i in range(n):
    for j in range(n):
        for k in range(sum_x+1):
            dp[i+1][k][j] += dp[i][k][j]
            if k + x[i] > sum_x:
                continue
            dp[i+1][k+x[i]][j+1] += dp[i][k][j]
            
ans = 0

for i in range(n):
    if a*(i+1) > sum_x:
        break
    ans += dp[n][a*(i+1)][i+1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

ans = 0
for i in range(1, n+1):
    b = list(combinations(x, i))
    for j in range(len(b)):
        cnt = 0
        for k in range(len(b[j])):
            cnt += b[j][k]
        if cnt == a * i:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
lists=list(map(int,input().split()))
x=max(lists)
dp=[[[0 for i in range(2602)] for j in range(51)] for _ in range(51)]
dp[0][0][0]=1
#dp[i][j][k] で0からi番目のカードまでのうちで　ｊ枚を選択して、その時に選んだ数の合計がsとなるような方法の総数を刺すことにする
for i in range(n+1):
    for j in range(n+1):
        for k in range(n*x+1):
            if i>=j and i>=1 and k<lists[i-1]:
                dp[i][j][k]=dp[i-1][j][k]
            elif i>=j and j>=1and k>=lists[i-1]:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-lists[i-1]]
ans=0
for i in range(1,n+1):
    ans+=dp[n][i][a*i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# C-高橋くんとカード
n,a=map(int,input().split())
lists=list(map(int,input().split()))
dp=[[[0 for i in range(2602)] for j in range(51)] for _ in range(51)]
dp[0][0][0]=1
#dp[i][j][k] で0からi番目のカードまでのうちで　ｊ枚を選択して、その時に選んだ数の合計がsとなるような方法の総数を刺すことにする
for i in range(n+1):
    for j in range(n+1):
        for k in range(2602):
            if i>=j and i>=1 and k<lists[i-1]:
                dp[i][j][k]=dp[i-1][j][k]
            elif i>=j and j>=1and k>=lists[i-1]:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-lists[i-1]]
ans=0
for i in range(1,n+1):
    ans+=dp[n][i][a*i]
print(ans)

Submission status: Time Limit Exceeded

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

dp1 = [[0 for i in range(N + 1)] for j in range(50 * N + 1)] #[Sum, #Cards]
dp2 = [[0 for i in range(N + 1)] for j in range(50 * N + 1)] #[Sum, #Cards]
dp1[0][0]=1

for i in range(N):#Focus Card [x_i]
  #Not Use x_i
  for j in range(N+1):
    for k in range(50 * j + 1):
        dp2[k][j] = dp1[k][j]
  #Use x_i
  for j in range(N):
    for k in range(50 * j + 1):
      if k + X[i] <= 50*N:
        dp2[k + X[i]][j+1] += dp1[k][j]
  for j in range(N+1):
    for k in range(50 * j + 1):
        dp1[k][j] = dp2[k][j]

res = 0
for i in range(1, N+1):
  res += dp1[i*A][i]
print(res)

Submission status: Time Limit Exceeded

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

dp1 = [[0 for i in range(N + 1)] for j in range(50 * N + 1)] #[Sum, #Cards]
dp2 = [[0 for i in range(N + 1)] for j in range(50 * N + 1)] #[Sum, #Cards]
dp1[0][0]=1

for i in range(N):#Focus Card [x_i]
  #Not Use x_i
  for j in range(N+1):
    for k in range(50 * N + 1):
        dp2[k][j] = dp1[k][j]
  #Use x_i
  for j in range(N):
    for k in range(50 * N + 1):
      if k + X[i] <= 50*N:
        dp2[k + X[i]][j+1] += dp1[k][j]
  for j in range(N+1):
    for k in range(50 * N + 1):
        dp1[k][j] = dp2[k][j]

res = 0
for i in range(1, N+1):
  res += dp1[i*A][i]
print(res)

Submission status: Time Limit Exceeded

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

dp1 = [[0 for i in range(N + 1)] for j in range(50 * N + 1)] #[Sum, #Cards]
dp2 = [[0 for i in range(N + 1)] for j in range(50 * N + 1)] #[Sum, #Cards]
dp1[0][0]=1

for i in range(N):#Focus Card [x_i]
  for j in range(N+1):
    for k in range(50 * N + 1):
        dp2[k][j] = 0
  #Not Use x_i
  for j in range(N):
    for k in range(50 * N + 1):
        dp2[k][j] += dp1[k][j]
  #Use x_i
  for j in range(N):
    for k in range(50 * N + 1):
      if k + X[i] <= 50*N:
        dp2[k + X[i]][j+1] += dp1[k][j]
  for j in range(N+1):
    for k in range(50 * N + 1):
        dp1[k][j] = dp2[k][j]

res = 0
for i in range(1, N+1):
  res += dp1[i*A][i]
print(res)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int,input().split())
X = list(map(int,input().split()))
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):
    x = X[i-1]
    for j in range(1,N+1):
        for k in range(N*50+1):
            if k < x:
                dp[i][j][k] = dp[i-1][j][k]
                
            elif j > i:
                dp[i][j][k] = 0
                
            else: 
                dp[i][j][k] += dp[i-1][j][k] + dp[i-1][j-1][k-x]
ans = 0
for i in range(1,N+1):
    ans += dp[N][i][A*i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, starmap

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

coefficient = 1  # Aの係数
result = 0
while coefficient <= N:
    for r in range(1, N+1):
        multiple_of_a = coefficient * A
        combis_sums = map(sum, combinations(x_list, r))
        for combi_sum in combis_sums:
            if combi_sum == multiple_of_a:
                result += 1
        coefficient += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

count=0
for i in range(1,N+1):
    lst=list(itertools.combinations(x,i))
    for comb in lst:
        ave=sum(comb)/len(comb)
        if(ave==float(A)):
            count+=1
print(count)

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

MAX = N * K
# dp[i][j][k] := i枚目までからj枚取って、合計をkにする通り数
dp = list3d(N+1, N+1, MAX+1, 0)
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(i+1):
        for k in range(MAX+1):
            dp[i+1][j][k] += dp[i][j][k]
            if j+1 <= N and k+a <= MAX:
                dp[i+1][j+1][k+a] += dp[i][j][k]
ans = 0
for j in range(1, N+1):
    # 1枚以上取った時の、平均がKになる所 → j枚取って合計がj*Kの所 を合計する
    ans += dp[N][j][j*K]
print(ans)

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

total = sum(A)
# dp[i][j][k] := i枚目までからj枚取って、合計をkにする通り数
dp = list3d(N+1, N+1, total+1, 0)
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(N+1):
        for k in range(total+1):
            dp[i+1][j][k] += dp[i][j][k]
            if j+1 <= N and k+a <= total:
                dp[i+1][j+1][k+a] += dp[i][j][k]
ans = 0
for j in range(1, N+1):
    if j*K <= total:
        # 1枚以上取った時の、平均がKになる所 → j枚取って合計がj*Kの所 を合計する
        ans += dp[N][j][j*K]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    def recur(i, n, total):
        # print("i, n, total", i, n, total)

        if not TABLE[i][n][total] == -1:
            # print('cache!')
            return TABLE[i][n][total]

        if not i < N:
            if n > 0 and total == A * n:
                TABLE[i][n][total] = 1
                return 1
            TABLE[i][n][total] = 0
            return 0

        ans1 = recur(i + 1, n, total)
        ans2 = recur(i + 1, n + 1, total + XS[i])

        # print(ans1, ans2)

        return ans1 + ans2

    N, A = tuple(map(int, input().split()))
    XS = tuple(map(int, input().split()))

    TABLE = []
    for _ in range(N + 1):
        lines = [[-1 for x in range(N * 50 + 1)] for y in range(N + 1)]
        TABLE.append(lines)

    return recur(0, 0, 0)


if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

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

def ls(j,k,s,x):
  if j==0 and k==0 and s==0:
    return 1
  elif j>=1 and s<x[j-1]:
    return ls(j-1,k,s,x)
  elif j>=1 and k>=1 and s>=x[j-1]:
    return ls(j-1,k,s,x)+ls(j-1,k-1,s-x[j-1],x)
  else:
    return 0
              
way=0
for k in range(N+1)[1:]:
    way+=ls(N,k,k*A,x)
print(way)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main(n, a, x):
    SUM_MAX = max(a, max(x)) * n + 1
    dp = np.zeros(shape=(n + 1, n + 1, SUM_MAX), dtype=int)

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

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


if __name__ == '__main__':
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
    print(main(N, A, X))

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, a = map(int, input().split())
integers = list(int(x) - a for x in input().split())
count = 0
for i in range(1, len(integers)+1):
    for combs in itertools.combinations(integers, i):
        av = sum(combs) / i
        if av == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, a = map(int, input().split())
integers = list(map(int, input().split()))
count = 0
for i in range(1, len(integers)+1):
    for combs in itertools.combinations(integers, i):
        av = sum(combs) / i
        if av == a:
            count += 1

print(count)

Submission status: Time Limit Exceeded

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

def Count(j,k,s):
	if(j==0 and k==0 and s==0):
		return 1
	elif(j >= 1 and s < x[j-1]):
		return Count(j-1,k,s)
	elif(j >= 1 and k>=1 and s >= x[j-1]):
		return Count(j-1,k,s) + Count(j-1,k-1,s-x[j-1])
	elif(j < k):
		return 0
	else:
		return 0

sum=0
for i in range(1,n+1):
	sum += Count(n,i,i*a)
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import math

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

bin_str = ''
for i in range(n):
  bin_str += '1'

patterns = []
for i in range(int(bin_str, 2)):
  b = format(i+1, 'b')
  r = []
  lb = list(b)
  lb.reverse()
  for index, bi in enumerate(lb):
    if bi == '1':
      r.append(x[index])
  patterns.append(r)
  
count = 0
for p in patterns:
  s = sum(p) / len(p)
  if s < a:
    continue
  if math.ceil(s) == a:
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import math


class DFS:
    def __init__(self, average, numbers):
        self.average = average
        self.numbers = sorted([n for n in numbers if n != average], reverse=True)
        self.length = len(self.numbers)
        self.sum = average * self.length
        self.pre_patterns = int(math.pow(2, numbers.count(self.average))) - 1

    def _dfs(self, index, sum, picked):
        patterns = 0
        sum_if_added = sum + self.numbers[index]
        sum_if_not_added = sum
        picked_if_added = picked + 1
        picked_if_not_added = picked
        if index == self.length - 1:
            if self.average == sum_if_added / picked_if_added:
                patterns += 1
            if picked_if_not_added != 0 and self.average == sum_if_not_added / picked_if_not_added:
                patterns += 1
            return patterns
        else:
            if sum_if_added <= self.sum:
                patterns += self._dfs(index=index + 1, sum=sum_if_added, picked=picked_if_added)
            patterns += self._dfs(index=index + 1, sum=sum_if_not_added, picked=picked_if_not_added)
            return patterns

    def calc_patterns(self):
        if self.length > 0:
            dfs = self._dfs(index=0, sum=0, picked=0)
        else:
            dfs = 0
        patterns_by_dfs = (self.pre_patterns + 1) * dfs
        return self.pre_patterns + patterns_by_dfs


def main(n, a, x):
    dfs = DFS(average=a, numbers=x)
    result = dfs.calc_patterns()
    return result


if __name__ == '__main__':
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
    print(main(N, A, X))

Submission status: Time Limit Exceeded

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


def main():
    n, a = map(int, input().split())
    x = tuple(map(int, input().split()))

    sm_mx = sum(x)

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

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

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sm_mx + 1):
                if sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]

    ans = 0
    for i in range(1, n + 1):
        if i > sm_mx / a:
            break
        ans += dp[n][i][i*a]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import floor


def main():
    n, a = map(int, input().split())
    x = tuple(map(int, input().split()))

    sm_mx = sum(x)

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

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

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sm_mx + 1):
                if sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]

    ans = 0
    i_mx = min(floor(sm_mx / a), n)
    for i in range(1, i_mx + 1):
        ans += dp[n][i][i*a]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, a = map(int, input().split())
    x = tuple(map(int, input().split()))

    sm_mx = sum(x)

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

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

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sm_mx + 1):
                if sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]

    ans = 0
    for i in range(1, n + 1):
        if i > sm_mx / a:
            break

        ans += dp[n][i][i*a]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, a = map(int, input().split())
    x = tuple(map(int, input().split()))

    sm_mx = sum(x)

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

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

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sm_mx + 1):
                if i >= 1 and sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif i >= 1 and j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]
                else:
                    dp[i][j][sm] = 0

    ans = 0
    for i in range(1, n + 1):
        if i <= sm_mx / a:
            ans += dp[n][i][i*a]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    sm_mx = 50 * n

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

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

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sm_mx + 1):
                if i >= 1 and sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif i >= 1 and j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]
                else:
                    dp[i][j][sm] = 0

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    ans = 0
    for pat in range(1, 1 << n):
        cnt = 0
        sm = 0
        i = 0
        while pat:
            if pat % 2:
                cnt += 1
                sm += x[i]
            pat //= 2
            i += 1

        if sm / cnt == a:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# C - 高橋君とカード / Tak and Cards

#import numpy as np
import math

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

# 数列aと整数Aを与えると、aからいくつか取って合計Aにするパターンが何通りあるかを返す関数
def partial_sum(a,A):
    n = len(a)
    dp = [[0]*(A+2) for _ in range(n+2)] # dp[i+1][j] a[i]までの数からいくつか選んで総和をjにするパターンの数
    dp[0][0] = 1
    
    for i in range(n):
        for j in range(A+1):
            if j >= a[i]:
                dp[i+1][j] = dp[i][j-a[i]] + dp[i][j]
            else:
                dp[i+1][j] = dp[i][j]
                
    return dp[n][A]

x_diff = [a - A for a in x] # ここから合計0になるように取る。負の数列についてpartial_sumが動かないことに注意
x_diff_negative = [-a for a in x_diff if a < 0]
x_diff_positive = [a for a in x_diff if a > 0]

ans = 0
for i in range(1, min(sum(x_diff_negative), sum(x_diff_positive)) + 1):
    ans += partial_sum(x_diff_negative,i) * partial_sum(x_diff_positive,i) 

# 0の選び方
n_pattern_0 = 0
n_0 = x_diff.count(0)
if n_0 > 0:
    for i in range(1, n_0+1):
        n_pattern_0 += math.factorial(n_0) // (math.factorial(n_0-i) * math.factorial(i))

# ここまで数えた全てのパターンそれぞれについて、x_diff中の0をいくつか含めた別パターンがある
# 0単体で選ぶ方法もある
ans += (ans+1) * n_pattern_0
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# C - 高橋君とカード / Tak and Cards

#import numpy as np
import math

N, A = map(int, input().split())
#x = np.array(list(map(int, input().split())))
x = list(map(int, input().split()))

# 数列aと整数Aを与えると、aからいくつか取って合計Aにするパターンが何通りあるかを返す関数
def partial_sum(a,A):
    n = len(a)
    dp = [[0]*(A+2) for _ in range(n+2)] # dp[i+1][j] a[i]までの数からいくつか選んで総和をjにするパターンの数
    dp[0][0] = 1
    
    for i in range(n):
        for j in range(A+1):
            if j >= a[i]:
                dp[i+1][j] = dp[i][j-a[i]] + dp[i][j]
            else:
                dp[i+1][j] = dp[i][j]
                
    return dp[n][A]

#x_diff = x - np.array(A) # ここから合計0になるように取る。負の数列についてpartial_sumが動かないことに注意
x_diff = [a - A for a in x]
x_diff_negative = [-a for a in x_diff if a < 0]
x_diff_positive = [a for a in x_diff if a > 0]

ans = 0
for i in range(1, sum(x)):
    ans += partial_sum(x_diff_negative,i) * partial_sum(x_diff_positive,i) 

# 0の選び方
n_pattern_0 = 0
#n_0 = np.count_nonzero(x_diff == 0)
n_0 = x_diff.count(0)
if n_0 > 0:
    for i in range(1, n_0+1):
        n_pattern_0 += math.factorial(n_0) // (math.factorial(n_0-i) * math.factorial(i))

# ここまで数えた全てのパターンそれぞれについて、x_diff中の0をいくつか含めた別パターンがある
# 0単体で選ぶ方法もある
ans += (ans+1) * n_pattern_0
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# C - 高橋君とカード / Tak and Cards

import numpy as np
import math

N, A = map(int, input().split())
x = np.array(list(map(int, input().split())))

# 数列aと整数Aを与えると、aからいくつか取って合計Aにするパターンが何通りあるかを返す関数
def partial_sum(a,A):
    n = len(a)
    dp = [[0]*(A+2) for _ in range(n+2)] # dp[i+1][j] a[i]までの数からいくつか選んで総和をjにするパターンの数
    dp[0][0] = 1
    
    for i in range(n):
        for j in range(A+1):
            if j >= a[i]:
                dp[i+1][j] = dp[i][j-a[i]] + dp[i][j]
            else:
                dp[i+1][j] = dp[i][j]
                
    return dp[n][A]

x_diff = x - np.array(A) # ここから合計0になるように取る。負の数列についてpartial_sumが動かないことに注意
x_diff_negative = [-x for x in x_diff if x < 0]
x_diff_positive = [x for x in x_diff if x > 0]

ans = 0
for i in range(1, sum(x)):
    ans += partial_sum(x_diff_negative,i) * partial_sum(x_diff_positive,i) 

    
# 0の選び方
n_pattern_0 = 0
n_0 = np.count_nonzero(x_diff == 0)
if n_0 > 0:
    for i in range(1, n_0+1):
        n_pattern_0 += math.factorial(n_0) // (math.factorial(n_0-i) * math.factorial(i))

# ここまで数えた全てのパターンそれぞれについて、x_diff中の0をいくつか含めた別パターンがある
# 0単体で選ぶ方法もある
ans += (ans+1) * n_pattern_0
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain, combinations
if __name__ == "__main__":
    n, a = map(int, input().split())
    cards = list(map(int, input().split()))
    powercards = list(chain.from_iterable(combinations(cards, r) for r in range(len(cards) + 1)))
    powercards.pop(0)
    hands = 0
    for hand in powercards:
        sum = 0
        for card in hand:
            sum += card
        if (sum / len(hand) == float(a)):
            hands += 1
    print(hands)

Submission status: Time Limit Exceeded

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

XX = sum(X) + 1

dp = [[[0 for i in range(XX * 2)] for i in range(N + 3)] for i in range(N + 3)]

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

for i in range(N):
    for j in range(N + 1):
        for n in range(XX):
            dp[i + 1][j][n] += dp[i][j][n]
            dp[i + 1][j + 1][n + X[i]] += dp[i][j][n]

ans = 0
for i in range(1, N + 1):
    if i * A < XX:
        ans += dp[N][i][i * A]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N,A=map(int,input().split())

l=list(map(int,input().split()))
l.sort()
ans=[]

def dfs(num,i,count):
    num+=l[i]
    count+=1
    if num==A*count and num!=0:
        ans.append("A")#ここ何とかすれば終わり
    if num>A*count:
        return
    if i==len(l)-1:
        pass
    else:
        dfs(num,i+1,count)
    num-=l[i]
    count-=1
    if i==len(l)-1:
        pass
    else:
        dfs(num,i+1,count)

dfs(0,0,0)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

n, a = map(int, input().split())
x = sorted(list(map(int, input().split())))

max_x = max(x + [a])
x.insert(0, 0)

res_array = np.zeros((n+1, n+1, n*max_x+1))
for i in range(n+1):
    for j in range(n+1):
        for k in range(n*max_x+1):
            if i == 0 and j == 0 and k == 0:
                tmp = 1
            elif i >= 1 and j >= 1 and k >= x[i]:
                tmp = res_array[i-1][j][k] + res_array[i-1][j-1][k-x[i]]
            elif i >= 1:
                tmp = res_array[i-1][j][k]
            else:
                tmp = 0
            res_array[i][j][k] = tmp

res = 0
for j in range(1, n+1):
    res += res_array[-1, j, j*a]
print(int(res))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n, a = map(int, input().split())
X = list(map(int, input().split()))

ans = 0

for i in range(1, n+1):
    L = list(combinations(X, i))
    for l in L:
        if sum(l) / i == a:
            ans += 1
print(ans)