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

dp = [[[0 for x_sum in range(n*a+1)] for sentaku in range(n+1)] for syurui in range(n+1)]

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


#i種類のカードのうちj枚を使うときにできるsを求める
for i in range(1,n+1):
    for j in range(n+1):
        for k in range(n*a+1):
            #追加できない場合は前のをコピー
            if x[i-1] > k:
                dp[i][j][k] = dp[i-1][j][k]
            #追加できる場合は前の場合と、前の場合でさたに今のを追加したのの和
            elif x[i-1] <= k:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-x[i-1]]
            #それ以外　なにもしない
            else:
                pass

out = 0
i = 1
while 1:
    if i*a > n*a:
        break
    out += dp[n][i][i*a]
    i+=1

print(out)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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

x2 = [_ for _ in x]
x2.append(a)
max_x = max(x2)
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:

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

L = sum(X)

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

for i in range(N):
    for j in range(L+10):
        for k in range(N):
            dp[i+1][j][k] += dp[i][j][k]
            if j >= X[i]:
                dp[i+1][j][k+1] += dp[i][j-X[i]][k]
            
ans = 0
for k in range(1,N+1):
    if A*k > L:break
    ans += dp[N][A*k][k]
                
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
from math import factorial
n = list(map(int, input().split()))
x = np.array(list(map(int, input().split())))

x = x - n[1]
b = len(x) - np.count_nonzero(x)
x = [i for i in x if i != 0]
x = np.sort(x)

c = 0
for i in range(1, b + 1):
    c += factorial(b) / factorial(i) / factorial(b - i)

cnt = c
for i in range(2, n[0] + 1):
    if len(x) == 0:
        break
    a = np.sum(np.array(list(itertools.combinations(x, i))), axis = 1)
    if a[0] > 0:
        break
    cnt += (c + 1) * (len(a) - np.count_nonzero(a))
            
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
from math import factorial
n = list(map(int, input().split()))
x = np.array(list(map(int, input().split())))

x = x - n[1]
b = len(x) - np.count_nonzero(x)
x = [i for i in x if i != 0]
x = np.sort(x)

c = 0
for i in range(1, b + 1):
    c += factorial(b) / factorial(i) / factorial(b - i)

cnt = c
for i in range(2, n[0] + 1):
    for j in itertools.combinations(x, i):
        if j[0] > 0:
            break
        if sum(j) == 0:
            cnt += c + 1
            
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
from math import factorial
n = list(map(int, input().split()))
x = np.array(list(map(int, input().split())))

x = x - n[1]
b = len(x) - np.count_nonzero(x)
x = [i for i in x if i != 0]
x = np.sort(x)

c = 0
for i in range(1, b + 1):
    c += factorial(b) / factorial(i) / factorial(b - i)

cnt = c
for i in range(2, n[0] + 1):
    for j in itertools.combinations(x, i):
        if sum(j) > 0:
            continue
        if sum(j) == 0:
            cnt += c + 1
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import product

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

x_minus = sorted([a-xi for xi in x if xi < a])
x_plus = [xi-a for xi in x if xi > a]
x_a = n - len(x_minus) - len(x_plus)

sum_minus = []
for pro in product([0,1], repeat=len(x_minus)):
    sum_minus.append(np.dot(np.array(pro), x_minus))
sum_plus = []
for pro in product([0,1], repeat=len(x_plus)):
    sum_plus.append(np.dot(np.array(pro), x_plus))

np_minus = np.array(sorted(sum_minus))
np_plus = np.array(sorted(sum_plus))

count = 0
for i_minus in np_minus:
    count += sum(np_plus == i_minus)

print(count * (2 ** x_a) -1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
from math import factorial
n = list(map(int, input().split()))
x = np.array(list(map(int, input().split())))

x = x - n[1]
b = len(x) - np.count_nonzero(x)
x = [i for i in x if i != 0]

c = 0
for i in range(1, b + 1):
    c += factorial(b) / factorial(i) / factorial(b - i)

cnt = c
for i in range(1, n[0] + 1):
    for j in itertools.combinations(x, i):
        if sum(j) == 0:
            cnt += c + 1
print(int(cnt))

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):
    sum = 0
    num = 0
    for j in range(n):
        if (i>>j) & 1:
            sum += x[j]
            num += 1
    #print(sum, num, sum/num)
    if sum/num == a:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
n = list(map(int, input().split()))
x = np.array(list(map(int, input().split())))

x = x - n[1]

cnt = 0
for i in range(1, n[0] + 1):
    for j in itertools.combinations(x, i):
        if sum(j) == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())  # N枚数のカード, 平均をAにしたい
X = tuple(map(int, input().split()))  # N枚のカードの中身

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

dp[0][0][0] = 1  # 0枚の中から0枚選んで合計が0になる選び方が1通りある

for i in range(N):
    for j in range(N+1):
        for k in range(50*N+1):
            # if dp[i][j][k]:  # ここの分岐が分からん
            if k+X[i] < 50*N+2:
                dp[i+1][j][k] += dp[i][j][k]
                dp[i+1][j+1][k+X[i]] += dp[i][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:
n,a=map(int,input().split())
N=list(map(int,input().split()))
from functools import lru_cache
@lru_cache(maxsize=10000000)
def cal(a,b,c):
    if a==b==c==0:
        return 1
    if a>=1 and c<N[a-1]:
        return cal(a-1,b,c)
    if a>=1 and b>=1and c>=N[a-1]:
        return(cal(a-1,b,c)+cal(a-1,b-1,c-N[a-1]))
    else:
        return 0
    
ans=0
for k in range(n):
    ans+=cal(n,k+1,(k+1)*a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
N=list(map(int,input().split()))
from functools import lru_cache
@lru_cache(maxsize=1000000)
def cal(a,b,c):
    if a==b==c==0:
        return 1
    if a>=1 and c<N[a-1]:
        return cal(a-1,b,c)
    if a>=1 and b>=1and c>=N[a-1]:
        return(cal(a-1,b,c)+cal(a-1,b-1,c-N[a-1]))
    else:
        return 0
    
ans=0
for k in range(n):
    ans+=cal(n,k+1,(k+1)*a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
N=list(map(int,input().split()))
from functools import lru_cache
@lru_cache(maxsize=400000)
def cal(a,b,c):
    if a==b==c==0:
        return 1
    if a>=1 and c<N[a-1]:
        return cal(a-1,b,c)
    if a>=1 and b>=1and c>=N[a-1]:
        return(cal(a-1,b,c)+cal(a-1,b-1,c-N[a-1]))
    else:
        return 0
    
ans=0
for k in range(n):
    ans+=cal(n,k+1,(k+1)*a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
N=list(map(int,input().split()))
def cal(a,b,c):
    if a==b==c==0:
        return 1
    if a>=1 and c<N[a-1]:
        return cal(a-1,b,c)
    if a>=1 and b>=1and c>=N[a-1]:
        return(cal(a-1,b,c)+cal(a-1,b-1,c-N[a-1]))
    else:
        return 0
    
ans=0
for k in range(n):
    ans+=cal(n,k+1,(k+1)*a)
print(ans)

Submission status: Time Limit Exceeded

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

import itertools

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

max_x = max(max(x_list), A)
dp = [[[0 for s in range(N * max_x + 1)] for k in range(N + 1)] for j in range(N + 1)]
dp[0][0][0] = 1
ka_list = []

for j in range(N + 1):  # 何番目の数か
    x = x_list[j - 1]
    for k in range(N + 1):  # k枚選ぶとき
        for s in range(N * max_x + 1):
            if j == 0 and k == 0 and s == 0:
                dp[0][0][0] = 1
            elif j >= 1 and s < x:
                # オーバーするので選べない
                # ひとつ前と同じになる
                dp[j][k][s] = dp[j - 1][k][s]
            elif j >= 1 and k >= 1 and s >= x:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x]
            else:
                dp[j][k][s] = 0

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

Submission status: Time Limit Exceeded

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

temp = x + [A]

X = max(temp)

m = N * X

dp = [[[0]*(m+1) for k in range(N+1)] for j in range(N+1)]

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

res = 0

for j in range(N+1):
    for k in range(N+1):
        for s in range(m+1):
            if (j >= 1) & (s < x[j-1]):
                dp[j][k][s] = dp[j-1][k][s]
            elif (j >= 1) & (k >= 1) & (s >= x[j-1]):
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]

        if (k >= 1) & (j == N):
            res += dp[N][k][k*A]

print(res)

Submission status: Time Limit Exceeded

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

temp = x + [A]

X = max(temp)

m = N * X

dp = [[[0]*(m+1) for k in range(N+1)] for j in range(N+1)]

for j in range(N+1):
    for k in range(N+1):
        for s in range(m+1):
            if (j == 0) & (k == 0) & (s == 0):
                dp[j][k][s] = 1
            elif (j >= 1) & (s < x[j-1]):
                dp[j][k][s] = dp[j-1][k][s]
            elif (j >= 1) & (k >= 1) & (s >= x[j-1]):
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]

res = 0

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,A = inpl()
x = inpl()
dp = [[[0 for _ in range(n+5)] for i in range(3005)] for j in range(n+5)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(sum(x)+1):
        for k in range(n):
            if j >= x[i]:
                dp[i+1][j][k+1] = dp[i][j-x[i]][k] + dp[i][j][k+1]
            else:
                dp[i+1][j][k] = dp[i][j][k]
# for i in range(n+1):
#     print(dp[i][:50])
ans = 0
for j in range(1,sum(x)+1):
    for k in range(1,n+1):
        if j/k == A:
            ans += dp[n][j][k]
print(ans)

Submission status: Time Limit Exceeded

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


def solve():
    N, A = list(map(int, sys.stdin.readline().split()))
    Xs = list(map(int, sys.stdin.readline().split()))
    # dp[i][j][k] := 左からi枚目までに、j枚を選んで、選んだカードの総和がk  (iは0-origin)
    dp = [[[0]*(N*50+1) for _ in range(0, N+1)] for __ in range(0, N)]
    dp[0][0][0] = 1
    dp[0][1][Xs[0]] = 1

    for i in range(1, N):
        for j in range(0, N):
            for k in range(N*50+1):
                dp[i][j][k] += dp[i-1][j][k]
                if k+Xs[i] < N*50+1:
                    dp[i][j+1][k+Xs[i]] += dp[i-1][j][k]

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

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def f(n,x,i):
    if n == 0:
        if i != 0:
            if x/i == m:
                return 1
        return 0
    if memo[n-1][i][x] != -1 :
        if memo[n-1][i][x] > 0:
            return memo[n-1][i][x]
    memo[n-1][i][x] = f(n-1,x,i)+f(n-1,x+a[n-1],i+1)
    return memo[n-1][i][x]

n, m= map(int,input().split())
a = list(map(int,input().split()))
memo = [[[-1 for _ in range(sum(a)+1)]for i in range(n)]for i in range(n)]
print(f(n,0,0))

Submission status: Time Limit Exceeded

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

x0 = X.count(0)
xm = [-x for x in X if x < 0][::-1]
xp = [x for x in X if x > 0]

em = [0] * (sum(xm) + 1)
ep = [0] * (sum(xp) + 1)

if len(xm) <= len(xp):
    x, e, xa = xm, em, xp
else:
    x, e, xa = xp, ep, xm

for i in range(1, 2**len(x)):
    temp, bit = 0, i
    for j in range(len(x)):
        if (bit >> j) % 2 != 0:
            temp += x[j]
    e[temp] += 1

ans = 0
for k in [l for l in range(len(e)) if e[l] > 0]:
    xac = [x for x in xa if x <= k]
    ansk = 0
    for i in range(1, 2**len(xac)):
        temp, bit = 0, i
        for j in range(len(xac)):
            if (bit >> j) % 2 != 0:
                temp += xa[j]
        if temp == k:
            ansk += 1
    ans += e[k] * ansk

print(2**x0 * (1 + ans) - 1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

cnt = 0
for i in range(1, N + 1):
    for j in itertools.combinations(x, i):
        if sum(j) == i * A:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

s = x

ans = 0

#print(s[0],s[1],s[2])

for i in range(2**(len(s))):
    tmp = i
    #print(tmp,tmp,tmp)
    temp = 0
    cnt = 0
    for j in range(len(s)):
        #print(ans)
        #temp += int(s[j])
        #print(temp)
        if tmp % 2 == 0:
            #temp = temp * 10
            #print(0)
            b = 1
            #if j == len(s)-2:
                #ans += temp + int(s[j+1])
        else:
            #ans += s[i]
            temp += x[j]
            cnt += 1
            #ans += temp
            #temp = 0
        if j == len(s)-1:
            #ans += temp + int(s[j+1])
            if cnt == 0:
                continue
            #print(temp,cnt,a)
            if temp / cnt == a:
                #print(temp,cnt)
                ans += 1
        tmp = tmp // 2
    
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

def dfs(sum,i,cnt):
	if i == N:
		if cnt != 0 and sum / cnt == A:
			return 1
		else:
			return 0

	return dfs(sum+L[i], i+1, cnt+1) + dfs(sum, i+1, cnt)


print(dfs(0,0,0))

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools,pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, A = LI()
X = LI()

"""
1枚以上選んで平均をAにする
カードは50枚ある
選ぶか選ばないかで2**50通りある
2**10が1024だとすると
10**3を5回なので間に合わない

ソートして両端を求めるか
そもそも、50枚選んでAになるということ
50までなので、
A4なら
1 7
2 6
3 5
4 4
がある

7 9 8 9
の例で考えると
7 9が2通り
8が1通りある
7 9 7 9 7 9 7 9 7 9 だった場合

"""
ans = 0
def main():
    global ans
    def dfs(card_num, selected_cards):
        global ans
        if card_num == N:
            if selected_cards == []:
                return
            average = sum(selected_cards) / len(selected_cards)
            #  print(average, selected_cards)
            if average == A:
                #  print('equal')
                ans += 1
            return
        dfs(card_num+1, selected_cards + [X[card_num]])
        dfs(card_num+1, selected_cards)
    dfs(0, [])
if __name__ == "__main__":
    main()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, Counter

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools                                                                
                                                                                
def solution(data, a):                                                          
    combs = [data, ]                                                            
    for x in xrange(1, len(data)):                                              
        combs.extend(list(itertools.combinations(data, x)))                     
    result = 0                                                                  
    for c in combs:                                                             
        if float(sum(c)) / float(len(c)) == float(a):                           
            result += 1                                                         
    print(result)                                                               
                                                                                
                                                                                
def main():                                                                     
    n, a = [int(x) for x in raw_input().split()]                                
    solution([int(x) for x in raw_input().split()], a)                          
                                                                                
main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, A = map(int,input().split())
X = list(map(int,input().split()))
ans = 0
for pattern in itertools.product(range(2), repeat=N):
    s = 0
    t = 0
    for p, x in zip(pattern, X):
        if p == 1:
            s += x
            t += 1
    if t == 0:
        continue
    if s / t == A:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

count = 0
for i in range(2**N):
    total = []
    for j in range(N):
        if ((i>>j) & 1):
            total.append(X[j])

    if len(total) > 0:
        if sum(total) / len(total) == 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(' ')))
X = max(x)
X = max(X, A)

dp = [[[0 for s in range(N * X + 1)] for k in range(N + 1)] for j 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]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif 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]]
#print(dp)
count = 0
for k in range(1, N + 1):
    #print(dp[N][k][k * A])
    count += dp[N][k][k * A]
print(count)

Submission status: Time Limit Exceeded

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

dp = [[[0 for s in range(N * X + 1)] for k in range(N + 1)] for j in range(N + 1)]

dp[0][0][0] = 1
for j in range(N + 1):
    for k in range(N + 1):
        for s in range(N * X + 1):
            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]]
#print(dp)
count = 0
for k in range(1, N + 1):
    #print(dp[N][k][k * A])
    count += dp[N][k][k * A]
print(count)

Submission status: Time Limit Exceeded

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

dp = [[[0 for _ in range(3010)] for __ in range(N+1)] for ___ in range(N+1)]

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

comb = []

for i in range(1,n+1):
    comb.append(list(itertools.combinations(nums,i)))

c = 0

l = []

for i in range(n):
    for j in comb[i]:
        l.append(list(j))

for i in l:
    if sum(i)/len(i) == a:
        c+= 1
        
print(c)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

V = []
for x in X:
    V.append(x - A)

ans = 0
for r in range(1, len(V)+1):
    C = list(combinations(V, r))
    for c in C:
        if sum(c) == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr

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

count = 0
for i in range(2**N):
    m = []
    for j in range(N):
        if ((i >> j) & 1):
            m.append(l[j])
    if len(m) != 0 and sum(m)/len(m) == A:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, average = map(int, input().split())
x = input().split()
all = 1  #全通りの変数
count = 0  #何通りかを数えていく変数

y = []
for i in range(n):
  y.append(int(x[i]) - average)

#全通りを計算する(2^n)
for i in range(n):
  all *= 2

#平均0となる回数を調べる
#yのj番目を選ぶか選ばないか。選ぶならbit[j] = 1, 選ばないならbit[j] = 0
for i in range(all):
  total = 0  #選んだ(x[i] - average)の和
  
  #i番目の値を2進数表現
  bit = str(bin(i))
  
  #左端の"0b"という文字列を削除
  bit = bit.lstrip("0")
  bit = bit.lstrip("b")
  
  #2進数表現をn桁に揃える
  bit = bit.rjust(n)
  
  #数え上げる
  for j in range(n):
    if bit[j] == "1":
      total += y[j]
  if total == 0:
    count += 1
    
print(count - 1)

Submission status: Time Limit Exceeded

Solution code:
#解説解答
n,a = map(int,input().split())
x = list(map(int,input().split()))
dp0 = [[0 for s in range(n*a+1)] for k in range(n+1)]
dp0[0][0] = 1
dp = dp0
for j in range(n):
  now = []
  for k in range(n+1):
    add = []
    for s in range(n*a+1):
      t = s-x[j]
      if t >= 0 and k >= 1:
        add.append( dp[k][s] + dp[k-1][t] )
      else:
        add.append( dp[k][s] )
    now.append(add)
  dp = now
ans = 0
for k in range(1,n+1):
  ans += dp[k][k*a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#解説解答
n,a = map(int,input().split())
x = list(map(int,input().split()))
dp0 = [[0 for s in range(n*a+1)] for k in range(n+1)]
dp0[0][0] = 1
dp = [dp0]
for j in range(n):
  now = [[] for k in range(n+1)]
  for k in range(n+1):
    for s in range(n*a+1):
      if s-x[j] >= 0 and k >= 1:
        now[k].append( dp[j][k][s] + dp[j][k-1][max(0,s-x[j])] )
      else:
        now[k].append( dp[j][k][s] )
  dp.append(now)
now = dp[n]
ans = 0
for k in range(1,n+1):
  ans += now[k][k*a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a = map(int,input().split())
c = list(map(int,input().split()))
def suc(time):
  now = n-1
  while True:
    if now == -1:
      return 'over'
      break
    if time[now] == 0:
      time[now] = 1
      return time
      break
    else:
      time[now] = 0
      now -= 1
time = [0 for _ in range(n)]
ans = 0
while time != 'over':
  now = 0
  cnt = 0
  for i in range(n):
    now += time[i] * c[i]
    cnt += time[i]
  if now == a * cnt:
    ans += 1
  time = suc(time)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
[n,a]=list(map(int,input().split()))
xlist=list(map(int,input().split()))
counter=0
wa=0
for kazu in range(1,2**(n)):
	keisu=[]
	for i in range(n):
		if i==0:
			kari=kazu
		keisu.append(kari%2)
		kari=kari//2
	keisu.reverse()
	wa=0
	for i in range(n):
		wa+=keisu[i]*xlist[i]
	kosu=keisu.count(1)
	if wa==kosu*a:
		counter+=1

print(counter)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N, K = map(int, input().split())
A = list(map(lambda x:int(x)-K, input().split()))

def Sum_list(i, s, L, ans):
    if i == len(L):
        ans.append(s)
        return ans
    ans = Sum_list(i+1, s, L, ans)
    ans = Sum_list(i+1, s+L[i], L, ans)
    return ans

def main():
    M = []
    P = []
    zero = 0
    for a in A:
        if a < 0:
            M.append(a)
        elif a > 0:
            P.append(a)
        else:
            zero += 1

    SM = Sum_list(0, 0, M, [])
    CM = Counter(SM)
    SP = Sum_list(0, 0, P, [])
    CP = Counter(SP)

    ans = 0
    for k, v in CP.items():
        if k == 0:
            continue
        if -k in CM.keys():
            ans += CM[-k]*v

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N, K = map(int, input().split())
A = list(map(lambda x:int(x)-K, input().split()))
A.sort()

M = []
P = []
zero = 0
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        zero += 1

def Sum_list(i, s, L, ans):
    if i == len(L):
        ans.append(s)
        return ans
    ans = Sum_list(i+1, s, L, ans)
    ans = Sum_list(i+1, s+L[i], L, ans)
    return ans


SM = Sum_list(0, 0, M, [])
CM = Counter(SM)
SP = Sum_list(0, 0, P, [])
CP = Counter(SP)

ans = 0
for k, v in CP.items():
    if k == 0:
        continue
    if -k in CM.keys():
        ans += CM[-k]*v

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

Submission status: Time Limit Exceeded

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

import numpy as np
import math
np_X = np.array(X)
count = 0

for j in range(math.floor((2 ** N) / 10000)+1):
  for i in range(10000):
#    print(j*10000 + i)
    i_2 = bin(j*10000 + i).replace('0b', '')
    i_2 = list(i_2)
    i_2_int = [int(s) for s in i_2]
#    print(i_2_int)
    while len(i_2_int)  < N:
      i_2_int.insert(0,0)  
    np_i_2_int = np.array(i_2_int)
#    np_product = np_i_2_int * np_X
  
    if len(np_i_2_int) == N + 1:
      break
    elif sum(np_i_2_int * np_X) == sum(np_i_2_int) * A:
      count += 1

print(count-1)

Submission status: Time Limit Exceeded

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

import numpy as np
np_X = np.array(X)
count = 0

for i in range(2 ** N):
  i_2 = bin(i).replace('0b', '')
  i_2 = list(i_2)
  i_2_int = [int(s) for s in i_2]
  while len(i_2_int)  < N:
    i_2_int.insert(0,0)  
  np_i_2_int = np.array(i_2_int)
  np_product = np_i_2_int * np_X
#  print(sum(np_product))
  
  if sum(np_product) == sum(np_i_2_int) * A:
    count += 1

print(count-1)

Submission status: Time Limit Exceeded

Solution code:
N, A = map(int, input().split())
X = list(map(int, input().split()))
#print(N)
#print(A)
#print(X[3])

import numpy as np
np_X = np.array(X)

count = 0

for i in range(2 ** N):
  i_2 = bin(i).replace('0b', '')
  i_2 = list(i_2)
  i_2_int = [int(s) for s in i_2]
  while len(i_2_int)  < N:
    i_2_int.insert(0,0)  
#  print(i_2_int)
#  print(X)
  np_i_2_int = np.array(i_2_int)
  np_product = np_i_2_int * np_X
#  print(sum(np_product))
  
  if sum(np_product) == sum(np_i_2_int) * A:
    count += 1

print(count-1)

Submission status: Time Limit Exceeded

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


ans = 0
for i in range(2 ** n):
    bit = format(i,'b')
    bit = bit.rjust(n,'0')
    lcs = 0
    cnt = 0
    for w in range(n):
        if bit[w]=='1':
            lcs += lst[w]
            cnt += 1
    
    if cnt != 0:
        if lcs / cnt == a:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, a = map(int, input().split())
x = [int(i) - a for i in map(int, input().split())]
x_minus = [xx for xx in x if xx < 0]
x_plus = [xx for xx in x if xx > 0]
x_zero = x.count(0)
plus_dict = {}
for i in range(1, 2 ** len(x_plus)):
    k = "0" * (len(x_plus) - len(bin(i)) + 2) + bin(i)[2:]
    calc = 0
    for j, kk in enumerate(k):
        if kk == "1":
            calc += x_plus[j]
    if calc not in plus_dict.keys():
        plus_dict[calc] = 1
    else:
        plus_dict[calc] += 1
minus_dict = {}
for i in range(1, 2 ** len(x_minus)):
    k = "0" * (len(x_minus) - len(bin(i)) + 2) + bin(i)[2:]
    calc = 0
    for j, kk in enumerate(k):
        if kk == "1":
            calc += x_minus[j]
    if calc not in minus_dict.keys():
        minus_dict[calc] = 1
    else:
        minus_dict[calc] += 1

ans = (2 ** x_zero) - 1
for key, value in minus_dict.items():
    if - key in plus_dict.keys():
        ans += value * plus_dict[-key] * ((2 ** x_zero))
print(ans)