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()))

# n,a=4,8
# x=[7,9,8,9]
cnt=0
sum=0
ans=0
for i in range(2**n):
    sum=0
    Ave=0
    cnt=0
    for j in range(n):
        if j!=n-1:
            if i>>j&1:
                sum+=x[j]
                cnt+=1

        else:
            if i>>j&1:
                sum+=x[j]
                cnt+=1
                Ave=sum/cnt
                if a==Ave:
                    ans+=1
            elif cnt>=1:
                Ave=sum/cnt
                if a==Ave:
                    ans+=1



print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, a = map(int, input().split())
    X = list(map(int, input().split()))
    MAX = n * a
    dp = [[[0] * (MAX + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 1
    for i in range(1, n + 1):
        x = X[i - 1]
        for k in range(n):
            for s in range(MAX):
                dp[i][k][s] += dp[i - 1][k][s]
                if s + x <= MAX:
                    dp[i][k + 1][s + x] += dp[i - 1][k][s]
    res = 0
    for k in range(1, n + 1):
        res += dp[-1][k][a * k]
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys
from collections import defaultdict
from operator import mul
from functools import reduce


def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def get_array():
    return list(map(int, sys.stdin.readline().strip().split()))


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)


def _main():
    N, A = get_ints()
    xn = get_array()

    xn.sort()

    xna = [i - A for i in xn]
    xnn = [i for i in xna if i < 0]
    xnp = [i for i in xna if i > 0]
    xn0 = [i for i in xna if i == 0]

    xn0_p = 0
    for i in range(len(xn0)):
        xn0_p += combinations_count(len(xn0), i)

    n = defaultdict(list)
    p = defaultdict(list)

    xnn = list(map(abs, xnn))

    for j in range(1, sum(xnn) + 1):
        gen = subset_sum(xnn, j)
        try:
            while 1:
                nl = gen.__next__()
                n[j].append(nl)
        except StopIteration:
            pass

    for k in n.keys():
        gen = subset_sum(xnp, k)
        try:
            while 1:
                pl = gen.__next__()
                p[k].append(pl)
        except StopIteration:
            pass

    ss = set(n.keys()) & set(p.keys())
    xn_p = 0
    for s in ss:
        xn_p += len(n[s]) * len(p[s])

    if xnn and xnp:
        print((xn0_p+1) * (xn_p+1) - 1)
    else:
        print(xn0_p)


if __name__ == "__main__":
    _main()

Submission status: Time Limit Exceeded

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

nega = []
posi = []
zero = 0
for x in X:
    if x < A: nega.append(A-x)
    elif A < x: posi.append(x-A)
    else: zero += 1

if len(nega) <= len(posi):
    arrf = sorted(nega)[::-1]
    arrg = sorted(posi)[::-1]
else:
    arrf = sorted(posi)[::-1]
    arrg = sorted(nega)[::-1]

from collections import defaultdict
from itertools import product
ans = 0
f = defaultdict(int)
g = defaultdict(int)
fmax = 0

for vr in product(range(2), repeat=len(arrf)):
    x = 0
    for i in range(len(vr)):
        x += vr[i] * arrf[i]
    if x == 0: continue
    f[x] += 1
    fmax = max(fmax, x)

for vr in product(range(2), repeat=len(arrg)):
    x = 0
    for j in range(len(vr)):
        x += vr[j] * arrg[j]
        if fmax < x: break
    if x == 0: continue
    g[x] += 1
    ans += f[x]

ans *= 2 ** zero
ans += 2 ** zero - 1
print(ans)

Submission status: Time Limit Exceeded

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

nega = []
posi = []
zero = 0
for x in X:
    if x < A: nega.append(A-x)
    elif A < x: posi.append(x-A)
    else: zero += 1

if len(nega) <= len(posi):
    arrf = sorted(nega)[::-1]
    arrg = sorted(posi)[::-1]
else:
    arrf = sorted(posi)[::-1]
    arrg = sorted(nega)[::-1]

from itertools import product
ans = 0
for v in product(range(2), repeat=len(arrf)):
    f = 0
    for i in range(len(v)):
        f += v[i] * arrf[i]
    if f == 0: continue
    for w in product(range(2), repeat=len(arrg)):
        g = 0
        for j in range(len(w)):
            g += w[j] * arrg[j]
        if g == 0: continue
        #if f < g: break
        if f == g: ans += 1

ans *= 2 ** zero
ans += 2 ** zero - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
cnt = 0
for i in range(1 << n):
    ans=[]
    for j in range(n):
        if (i >> j) & 1:
            ans.append(x[j])
    if ans and sum(ans)/len(ans) == a:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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

# dp[i][j][k]：　i枚目までのカードをj枚使用して合計kを作れる組み合わせ
dp = [[[0] * (3001) for j in range(n+1)] for i in range(n+1)]
dp[0][0][0] = 1

for i in range(n):
    _x = x[i]
    for j in range(n):
        for k in range(2501):
            dp[i+1][j+1][k+_x] += 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)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
c = 0
for i in range(1, 2**N):
  l, S  = 0, 0
  for j in range(N):
    if (i>>j)&1:
      l += 1
      S += X[j]
  if S/l == A:
    c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# template: v1.2

import io
import sys
import math
import numpy as np
import itertools
from collections import defaultdict

def solve(n,a,x_lst):
    # implement process
    t_start(9)
    t_start()
    
    cnt = 0
    x_lst.sort()
    M_lst,L_lst,R_lst = [],[],[]
    for x in x_lst:
        if x == a:
            M_lst.append(x)
        elif x < a:
            L_lst.append(x)
        else:
            R_lst.append(x)

    for i in range(len(L_lst)):
        L_lst[i] = a-L_lst[i]
    for i in range(len(R_lst)):
        R_lst[i] = R_lst[i]-a
    
    t_end("start")
    t_start()
    # Process Middle
    m_sum = 0
    for i in range(1,len(M_lst)+1):
        m_sum += math.factorial(len(M_lst)) / math.factorial(i) / math.factorial(len(M_lst) - i)

    if len(L_lst) == 0 or len(R_lst) == 0:
        return int(m_sum)

    t_end("middle")
    t_start()
    l_dd = defaultdict(lambda: 0) 
    r_dd = defaultdict(lambda: 0) 
    # process L-R
    for i in range(1,len(L_lst)+1):
        for lt in itertools.combinations(L_lst,i):
            l_dd[sum(lt)] +=1
    t_end("left")
    t_start()
    for i in range(1,len(R_lst)+1):
        for lt in itertools.combinations(R_lst,i):
            r_dd[sum(lt)] +=1
    t_end("right")
    t_start()
    lr_sum = 0
    for k,lv in l_dd.items():
        if k in r_dd:
            rv = r_dd[k]
            lr_sum += lv * rv
    t_end("LR calc")
    ans = 0
    ans = m_sum + lr_sum + m_sum * lr_sum
    
    t_end("end",9)
    return int(ans)


import time
time_start = [0] * 10**3
def t_start(i=0):
    if _DEB: time_start[i] = time.perf_counter()
def t_end(str="",i=0):
    if _DEB: print(f"time {str}: {time.perf_counter() - time_start[i]}")

def main():
    # input
    n,a,*x_lst = map(int,sys.stdin.read().split()) #一括で一部リスト化
    # process
    ans = str( solve(n,a,x_lst ) )
    
    # output
    print(ans)
    return ans
        
### DEBUG I/O ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
50 40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
"""
_EXPECTED = """\
19
"""

def logd(str):
    if _DEB: print(f"[deb] {str}")

### MAIN ###
if __name__ == "__main__":
    if _DEB:
        sys.stdin = io.StringIO(_INPUT)
        print("!! Debug Mode !!")

    ans = main()

    if _DEB:
        print()
        if _EXPECTED.strip() == ans.strip(): print("!! Success !!")
        else: print(f"!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# template: v1.2

import io
import sys
import numpy as np
import itertools
def solve(n,a,x_lst):
    # implement process
    cnt = 0
    for i in range(1,n+1):
        for lt in itertools.combinations(x_lst,i):
            if np.average(lt) == a:
                cnt+=1
    return cnt

def main():
    # input
    n,a,*x_lst = map(int,sys.stdin.read().split()) #一括で一部リスト化
    # process
    ans = str( solve(n,a,x_lst ) )
    
    # output
    print(ans)
    return ans
        
### DEBUG I/O ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
16 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
"""
_EXPECTED = """\
5

"""

def logd(str):
    if _DEB: print(f"[deb] {str}")

### MAIN ###
if __name__ == "__main__":
    if _DEB:
        sys.stdin = io.StringIO(_INPUT)
        print("!! Debug Mode !!")

    ans = main()

    if _DEB:
        print()
        if _EXPECTED.strip() == ans.strip(): print("!! Success !!")
        else: print(f"!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")

Submission status: Time Limit Exceeded

Solution code:
import copy
n, a = map(int, input().split())
X = sorted(list(map(int, input().split())))

#Lis = [[av1, num_of_num1], ...]
Lis = [[0, 0], [X[0], 1]]
for i in range(1, n):
    x = X[i]
    temp = copy.deepcopy(Lis)
    for total, num_of_num in Lis:
        num_of_num += 1
        total += x
        if total <= num_of_num * a:
            temp.append([total, num_of_num])
        #print(Lis)
    Lis = temp

ans = -1
for total, num_of_num in Lis:
    if total == num_of_num * a:
        ans += 1
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 _ 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(i+1):
        for k in range(n*a+1):
            if k+x[i-1]<=n*a:
                if j>=1:
                    dp[i][j][k+x[i-1]]+=dp[i-1][j-1][k]
            dp[i][j][k]+=dp[i-1][j][k]
ans=0
for i in range(1,n+1):
    ans+=dp[n][i][i*a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


noz=[x-a for x in cards].count(0)
pl=[x-a for x in cards if x-a>0]
nl=[a-x for x in cards if x-a<0]
sl=[pl,nl][len(nl)<=len(pl)]
ll=[pl,nl][len(pl)<len(nl)]

sl.sort()
ll.sort()

sumfunc = lambda n, l: sum([l[x]*((n>>x)&1) for x in range(len(l))])

sumsl=[0 for _ in range(sum(sl))]
sumll=[0 for _ in range(sum(ll))]

for i in range(1,2**len(sl)):
    sumsl[sumfunc(i,sl)-1]+=1

for i in range(1,2**len(ll)):
    sumll[sumfunc(i,ll)-1]+=1

count=sum([x*y for x,y in zip(sumsl, sumll)])
# count=0
# p=sum([not sumsl[-1]<sumfunc(2**i,ll) for i in range(1,len(ll)+1)])
# q=sum([sumsl[0]>=sumfunc(2**i-1,ll) for i in range(1,len(ll)+1)])
# count=[sumfunc(j,ll) in sumsl for j in range(2**q-1,2**p)].count(True)

print((count+1)*(2**noz)-1)

Submission status: Time Limit Exceeded

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

counter = 0
cnt = Counter(X)
for num_of_num in range(1, n+1):
    target = a * num_of_num
    for pattern in cmb(X, num_of_num):
        if sum(pattern) == target:
            counter += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
X = tuple(map(int, input().split()))
X = sorted(X)

from collections import deque
ans = 0
for i in range(n):
    st = deque([[i, 1, X[i]]])
    while st:
        idx, count, s = st.pop()
        if count*a == s:
            ans += 1
        elif count*a < s:
            continue
        
        for ni in range(idx+1, n):
            st.append([ni, count+1, s+X[ni]])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n,a = map(int,input().split())
l = list(map(int,input().split()))
r = []
for i in range(1,n+1):
	r.append(list(combinations(l,i)))
count = 0
for x in r:
	for j in x:
		avg = sum(j)/len(j)
		if(avg == a):
			count+=1
		else:
			pass
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
arr = list(map(int, input().split()))
w = 2 ** n

count = 0
for i in range(w):
    sub = []
    for j in range(n):
        if i & (1 << j):
            sub.append(arr[j])

    if len(sub) > 0 and sum(sub) / len(sub) == a:
        count += 1

print(count)

Submission status: Time Limit Exceeded

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

for i in range(N):
    X[i] -= A

lst = []
for i in range(1,1<<N):
    flag = [0]*N
    for j in range(N):
        if 1 & (i >> j):
            flag[j] = 1
    lst.append(flag)

ans = 0
for l in lst:
    sum = 0
    for k in range(N):
        if l[k] == 1:
            sum += X[k]
    if sum == 0:
        ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
for i in range(N):
    X[i] -= A

lst = []
for i in range(1,1<<N):
    flag = [0]*N
    for j in range(N):
        if 1 & (i >> j):
            flag[j] = 1
    lst.append(flag)

ans = 0
for l in lst:
    sum = 0
    for k in range(N):
        if l[k] == 1:
            sum += X[k]
    if sum == 0:
        ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

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

lst = []

for i in range(1,1<<N):
    flag = [0]*N
    for j in range(N):
        if 1 & (i >> j):
            flag[j] = 1
    lst.append(flag)

ans = 0
for l in lst:
    sum = 0
    cnt = 0
    for k in range(N):
        if l[k] == 1:
            sum += X[k]
            cnt += 1
    ave = sum / cnt
    if ave == A:
        ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, a = map(int, input().split())
x = list(map(int, input().split()))
xx = []
counter = 0

for i in range(1, n+1):
    for j in itertools.combinations(x, i):
        temp = list(j)
        if sum(temp)/ len(temp) == float(a):
            counter += 1

print(counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n, a = LI()
	x_list = LI()
	dp = np.full((n+1,n+1,n*max(x_list+[a])+1),-1)

	def dfs(j,k,s):
		dp_value = dp[j,k,s]
		if dp_value == -1:
			if j == 0 and k == 0 and s == 0:
				dp_value = 1
			elif j >= 1 and x_list[j-1] > s:
				dp_value = dfs(j-1, k, s)
			elif j >= 1 and k >= 1 and s >= x_list[j-1]:
				dp_value = dfs(j-1, k, s) + dfs(j-1, k-1, s-x_list[j-1])
			else:
				dp_value = 0
			dp[j,k,s] = dp_value
		return dp_value

	print(int(sum([dfs(n, k, k*a) for k in range(1,n+1)])))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n, a = LI()
	x_list = LI()
	x_list.sort()
	sum_list = deque([[i,x,1] for i, x in enumerate(x_list)])
	count = x_list.count(a)
	while sum_list:
		i, x, num = sum_list.popleft()
		for j in range(i+1,n):
			sum_tmp = x + x_list[j]
			if sum_tmp < a * (num+1):
				sum_list.append([j,sum_tmp,num+1])
			elif sum_tmp == a * (num+1):
				sum_list.append([j,sum_tmp,num+1])
				count += 1
			else:
				break
	print(count)
	







if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
x = list(map(int, input().split()))
s = sum(x)
dp = [[0] * (s * n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    dp[i][x[i - 1]] = 1
    for j in range(1, s + 1):
        dp[i][j] += dp[i - 1][j]
    for j in range(s + 1, s * n + 1):
        dp[i][j] = dp[i - 1][max(0, j - s - x[i - 1])] + dp[i - 1][j]
ans = 0
for i in range(1, n + 1):
    if i * a > s:
        print(ans)
        exit()
    ans += dp[n][i * a + (i - 1) * s]
print(ans)

Submission status: Time Limit Exceeded

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

dp = [[[0]*(50*(N+1)+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(N):
        for s in range(50*N+1):
            dp[i+1][k][s] += dp[i][k][s]
            dp[i+1][k+1][s+X[i]] += dp[i][k][s]

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

cnt = 0

for i in range(n+1):
    for v in itertools.combinations(x,i+1):
        if sum(v) == a*(i+1): #組み合わせのカードの平均がaと等しいならば
            cnt = cnt + 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

cnt = 0

for i in range(n+1):
    for v in itertools.combinations(x,i+1):
        if sum(v)/(i+1) == a: #組み合わせのカードの平均がaと等しいならば
            cnt = cnt + 1

print(cnt)

Submission status: Time Limit Exceeded

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

dp = [[[0] * (50 * (n + 10)) for _ in range(n + 10)] for _ in range(n + 10)]
dp[0][0][0] = 1

for i in range(n):
    for use in range(n):
        for total in range(n * a):
            dp[i + 1][use][total] += dp[i][use][total]
            dp[i + 1][use + 1][total + x[i]] += dp[i][use][total]

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()))

ans = 0
for i in range(2 ** n):
    pattern = [0] * n
    for j in range(n):
        if i >> j & 1:
            pattern[j] = 1

    val = 0
    for k in range(n):
        if pattern[k] == 1:
            val += x[k]

    if val != 0 and sum(pattern) != 0:
        if val / sum(pattern) == a:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
lst = [int(x) for x in input().split()]
ret = 0
for i in range(2 ** N):
    n = 0
    cnt = 0
    for j in range(N):
        if i >> j & 1:
            n += lst[j]
            cnt += 1
    if cnt > 0 and n / cnt == A:
        ret += 1
print(ret)

Submission status: Time Limit Exceeded

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


def main():
    N, A = map(int, input().split())
    x = list(map(int, input().split()))
    X = 50
    dp = [[[0]*(N*X +1) for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0][0] = 1
    for j in range(1,N+1):
        for k in range(N+1):
            for s in range(N*X+1):
                if s >= x[j-1] and k >= 1:
                    dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
                else:# x[j]を選ぶと合計sにできない
                    dp[j][k][s] = dp[j-1][k][s]
    ans = 0
    for i in range(N):
        ans += dp[N][i+1][(i+1)*A]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i, a in enumerate(X, 1):
  for j in range(N+1):
    for s in range(n+1):
      dp[i][j][s] = dp[i-1][j][s]
      if a <= s:
        dp[i][j][s] += dp[i-1][j-1][s-a]

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

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
dp2 = [[[] for i in range(N+1)] for k in range(N+1)]
for i in range(N+1):
    for j in range(1,N+1):
        if i == 0:
            dp2[i][j] = [0]
            continue
        if i == 1:
            dp2[i][j].append(x[j-1])
            if x[j-1] == A:
                ans += 1
            continue
        for k in range(1,j):
            for l in dp2[i-1][k]:
                dp2[i][j].append(l+x[j-1])
                if (l+x[j-1])/i == A:
                    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10**6)
 
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]
 
def dfs(i,s,no,total):
    global ans
 
    if i == l:
 
        if no != 0:
            if total/no == A:
                tmp = 1
                for i in range(l):
                    if s[i] > 0:
                        tmp *= cmb(num[i][1],s[i])
                ans = ans+tmp
        return
                
    for n in range(num[i][1]+1):
        dfs(i+1,s+[n],no+n,total+num[i][0]*n)
 
 
N,A = map(int,input().split())
x = list(map(int,input().split()))
 
num = list(zip(Counter(x).keys(),Counter(x).values()))
 
 
l = len(num)
ans = 0
dfs(0,[],0,0)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
a=float(a)
ans = 0
for i in range(2**n):
    k = []
    for j in range(i):
        if (i>>j)&1:
            k.append(x[j])
    l = len(k)
    if l:
        if sum(k)/l == a:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int,input().split())
numbers = list(map(int,input().split()))
how_many = 0
for i in range(1 << N):
    total = 0
    cnt = 0
    for j in range(N):
        if (i >> j)&1:
            cnt += 1
            total += numbers[j]
            
    if cnt > 0:
        average = total / cnt
        if average == float(A):
            how_many += 1
print(how_many)

Submission status: Time Limit Exceeded

Solution code:

N,A = map(int,input().split())
X =[int(x) for x in input().split()]
from itertools import product,compress
pattern = list(product({True,False},repeat=N))
cnt=0
for p in pattern:
    try:
        tmp = list(compress(X, p))
        if sum(tmp)/len(tmp)==A:
            cnt+=1
    except:
        continue
print(cnt)

Submission status: Time Limit Exceeded

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

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

def dfs(i,s,no,total):
    global ans

    if i == l:

        if no != 0:
            if total/no == A:
                tmp = 1
                for i in range(l):
                    if s[i] > 0:
                        tmp *= cmb(num[i][1],s[i])
                ans = ans+tmp
        return
                
    for n in range(num[i][1]+1):
        dfs(i+1,s+[n],no+n,total+num[i][0]*n)


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

num = list(zip(Counter(x).keys(),Counter(x).values()))


l = len(num)
ans = 0
dfs(0,[],0,0)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10**6)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

def dfs(i,s):
    global ans

    if i == l:

        nzero = 0
        tot = 0
        for i in range(l):
            if s[i] > 0:
                nzero += s[i]
            tot += s[i]*num[i][0]
        if nzero != 0:
            if tot/nzero == A:
                tmp = 1
                for i in range(l):
                    if s[i] > 0:
                        tmp *= cmb(num[i][1],s[i])
                ans = ans+tmp
        return
                
    for n in range(num[i][1]+1):
        dfs(i+1,s+[n])


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

num = list(zip(Counter(x).keys(),Counter(x).values()))


l = len(num)
ans = 0
dfs(0,[])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc044/tasks/arc060_a

from itertools import combinations


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

# print(n, a)
# print(x)
ans = 0
for k in range(1, n + 1):
    for comb in combinations(range(n), k):
        avg = 0
        for c in comb:
            avg += x[c]
        avg /= len(comb)
        if avg == a:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int,input().split())
lst = list(map(int,input().split()))
res = 0
for i in range(1,2**N):
    cards = []
    card_ave = 0
    for j in range(N):
        if ((i >> j) & 1):
            cards.append(lst[j])
    card_ave = sum(cards) / len(cards)
    if card_ave == A:
        res += 1
print(res)

Submission status: Time Limit Exceeded

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


ans = 0
for i in range(2 ** n):
    pattern = []
    for j in range(n):
        if i >> j & 1:
            pattern.append(x[j])
    if len(pattern) == 0:
        continue
    if sum(pattern) / len(pattern) == a:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,A=map(int,input().split())
    x=list(map(lambda x:int(x)-A,input().split()))
    d={}
    for i in range(2**(N//2)):
        tmp=0
        for j in range(N//2):
            if (i>>j)&1:
                tmp+=x[j]
        if tmp in d:
            d[tmp]+=1
        else:
            d[tmp]=1
    ans=0
    for i in range(2**(-(-N//2))):
        tmp=0
        for j in range(-(-N//2)):
            if (i>>j)&1:
                tmp+=x[N//2+j]
        if -tmp in d:
            ans+=d[-tmp]
    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,A=map(int,input().split())
    x=list(map(lambda x:int(x)-A,input().split()))
    d=defaultdict(int)
    for i in range(2**(N//2)):
        tmp=0
        for j in range(N//2):
            if (i>>j)&1:
                tmp+=x[j]
        d[tmp]+=1
    ans=0
    for i in range(2**(-(-N//2))):
        tmp=0
        for j in range(-(-N//2)):
            if (i>>j)&1:
                tmp+=x[N//2+j]
        ans+=d[-tmp]
    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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