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()))
M = max(x)
M = max(M, a)
dp = [[[0]*(n*M+1) for _ in range(n+1)] for _ in range(n+1)]

for j in range(n+1):
    for k in range(n+1):
        for s in range(n*M+1):
            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif 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]]
            else:
                dp[j][k][s] = 0
ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]
print(ans)

Submission status: Time Limit Exceeded

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

#dp[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0]*(a*n+1) for k in range(n+1) ] for j in range(n)]

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

res = 0
for i in range(1,n+1):
    res += dp[n-1][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[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0]*(a*n+1) for k in range(n+1) ] for j in range(n)]


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

res = 0
for i in range(1,n+1):
    res += dp[n-1][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[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0 for s in range(a*n+1) ] for k in range(n+1) ] for j in range(n)]

for j in range(n):
    dp[j][0][0]=1
    if x[0]<= a*n:
        dp[j][1][x[0]] = 1

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

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
count=0
N,A=map(int,input().split())
x=list(map(int, input().strip().split(' ')))

for i in range(N) :
	x1=list(itertools.combinations(x,i+1))
	for n in x1 :
		if A*(i+1)==sum(n) :
			count=count+1


print(count)

Submission status: Time Limit Exceeded

Solution code:
def func(n, a, x):
    # x.sort()
    dp = [[[0] * (sum(x) + 1)
           for _ in range(n + 1)]
          for _ in range(n)]
    # dp = [[[0] * (sum(x) + 1)] * (n + 1) for _ in range(n)]
    """
    dp = [[[0 for _ in range(sum(x) + 1)]
           for _ in range(n + 1)]
          for _ in range(n)]
    """
    """
    print(len(dp))
    print(len(dp[0]))
    print(len(dp[0][0]))
    print(dp)
    print(dp[0])
    print(dp[0][0])
    """
    # table[j][k][s] = x[j+1]までからk枚選んで、その和がsの場合の数
    # 0 <= j < N, 0 <= k <= N, s <= sum(x)
    # jはインデックスだが,kは選ぶ枚数なので「j < n」「k < n + 1」
    # dp[j][k][s] = dp[j-1][k][s] # x[j]を選ばないとき
    #               + dp[j-1][k-1][s-x[j]] #x[j]を選ぶ場合 (ただし1<=j<=k)
    # dp[0][0][0] = 1 #初期値(シード的な)
    # dp = 0 # 上記以外の場合
    dp[0][0][0] = 1
    # j == 0 での処理
    dp[0][1][x[0]] = 1

    for j in range(1, len(dp)):
        for k in range(len(dp[0])):
            for s in range(len(dp[0][0])):
                # 「j == 0」での事前処理が必要
                # if j > 0: # 解説では j > 0 and x[j] >= sらしい
                dp[j][k][s] += dp[j - 1][k][s]
                if k > 0 and s >= x[j]:
                    dp[j][k][s] += dp[j - 1][k - 1][s - x[j]]
                    # print("dp[{}][{}][{}]:{} <- dp[{}][{}][{}]:{} + {}".format(
                    # j, k, s, dp[j][k][s], j-1, k-1, s-x[j], dp[j-1][k-1][s-x[j]], x[j]))
                    # if dp[j][k][s] > 0:
                    # print("dp[{}][{}][{}]:{}---------------".format(j, k, s, dp[j][k][s]))
                    # else:
                    # print("dp[{}][{}][{}]:{}".format(j, k, s, dp[j][k][s]))
                    # for k in range(len(dp[0])):
                    # for j in range(len(dp)):
                    # print(dp[j][k])
    count = 0
    for k in range(1, min(len(dp[0]), len(dp[0][0]) // a + 1)):
        # print("dp[{}][{}][{}]:{}".format(n - 1, k, a * k, dp[n - 1][k][a * k]))
        count += dp[n - 1][k][a * k]
    return count


n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
print(func(n, a, x))
"""
print(func(4, 8, [7, 8, 9, 9]) == 5)  # 合計33
print(func(3, 8, [6, 6, 9]) == 0)  # 合計21
print(func(8, 5, [3, 6, 2, 8, 7, 6, 5, 9]) == 19)  # 合計46
print(func(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])
      == 8589934591)  # 合計46
"""

Submission status: Time Limit Exceeded

Solution code:
def func(n, a, x):
    # x.sort()
    dp = [[[0 for _ in range(sum(x) + 1)] for _ in range(n + 1)] for _ in range(n)]
    # table[j][k][s] = x[j+1]までからk枚選んで、その和がsの場合の数
    # 0 <= j < N, 0 <= k <= N, s <= sum(x)
    # jはインデックスだが,kは選ぶ枚数なので「j < n」「k < n + 1」
    # dp[j][k][s] = dp[j-1][k][s] # x[j]を選ばないとき
    #               + dp[j-1][k-1][s-x[j]] #x[j]を選ぶ場合 (ただし1<=j<=k)
    # dp[0][0][0] = 1 #初期値(シード的な)
    # dp = 0 # 上記以外の場合
    dp[0][0][0] = 1
    # j == 0 での処理
    dp[0][1][x[0]] = 1

    for j in range(1, len(dp)):
        for k in range(len(dp[0])):
            for s in range(len(dp[0][0])):
                # 「j == 0」での事前処理が必要
                # if j > 0: # 解説では j > 0 and x[j] >= sらしい
                dp[j][k][s] += dp[j-1][k][s]
                if k > 0 and s >= x[j]:
                    dp[j][k][s] += dp[j-1][k-1][s-x[j]]
                        #print("dp[{}][{}][{}]:{} <- dp[{}][{}][{}]:{} + {}".format(
                            #j, k, s, dp[j][k][s], j-1, k-1, s-x[j], dp[j-1][k-1][s-x[j]], x[j]))
                # if dp[j][k][s] > 0:
                    # print("dp[{}][{}][{}]:{}---------------".format(j, k, s, dp[j][k][s]))
                # else:
                    # print("dp[{}][{}][{}]:{}".format(j, k, s, dp[j][k][s]))
    # for k in range(len(dp[0])):
        # for j in range(len(dp)):
            # print(dp[j][k])
    count = 0
    for k in range(1, min(len(dp[0]), len(dp[0][0]) // a + 1)):
            # print("dp[{}][{}][{}]:{}".format(n - 1, k, a * k, dp[n - 1][k][a * k]))
        count += dp[n-1][k][a*k]
    return count

n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
print(func(n, a, x))
"""
print(func(4, 8, [7, 8, 9, 9]))#合計33
print(func(3, 8, [6, 6, 9]))#合計21
print(func(8, 5, [3,6,2,8,7,6,5,9]))#合計46
print(func(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]))#合計46
"""

Submission status: Time Limit Exceeded

Solution code:
def func(n, a, x):
    x.sort()
    dp = [[[0 for _ in range(sum(x) + 1)] for _ in range(n + 1)] for _ in range(n)]
    # table[j][k][s] = x[j+1]までからk枚選んで、その和がsの場合の数
    # 0 <= j < N, 0 <= k <= N, s <= sum(x)
    # jはインデックスだが,kは選ぶ枚数なので「j < n」「k < n + 1」
    # dp[j][k][s] = dp[j-1][k][s] # x[j]を選ばないとき
    #               + dp[j-1][k-1][s-x[j]] #x[j]を選ぶ場合 (ただし1<=j<=k)
    # dp[0][0][0] = 1 #初期値(シード的な)
    # dp = 0 # 上記以外の場合
    dp[0][0][0] = 1
    # j == 0 での処理
    dp[0][1][x[0]] = 1

    for j in range(1, len(dp)):
        for k in range(len(dp[0])):
            for s in range(len(dp[0][0])):
                # 「j == 0」での事前処理が必要
                # if j > 0: # 解説では j > 0 and x[j] >= sらしい
                dp[j][k][s] += dp[j-1][k][s]
                if j > 0 and k > 0 and s >= x[j]:
                    dp[j][k][s] += dp[j-1][k-1][s-x[j]]
                        #print("dp[{}][{}][{}]:{} <- dp[{}][{}][{}]:{} + {}".format(
                            #j, k, s, dp[j][k][s], j-1, k-1, s-x[j], dp[j-1][k-1][s-x[j]], x[j]))
                # if dp[j][k][s] > 0:
                    # print("dp[{}][{}][{}]:{}---------------".format(j, k, s, dp[j][k][s]))
                # else:
                    # print("dp[{}][{}][{}]:{}".format(j, k, s, dp[j][k][s]))
    # for k in range(len(dp[0])):
        # for j in range(len(dp)):
            # print(dp[j][k])
    count = 0
    for k in range(1, min(len(dp[0]), len(dp[0][0]) // a + 1)):
            # print("dp[{}][{}][{}]:{}".format(n - 1, k, a * k, dp[n - 1][k][a * k]))
        count += dp[n-1][k][a*k]
    return count

n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
print(func(n, a, x))
"""
print(func(4, 8, [7, 8, 9, 9]))#合計33
print(func(3, 8, [6, 6, 9]))#合計21
print(func(8, 5, [3,6,2,8,7,6,5,9]))#合計46
print(func(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]))#合計46
"""

Submission status: Time Limit Exceeded

Solution code:
def func(n, a, x):
    x.sort()
    dp = [[[0 for _ in range(sum(x) + 1)] for _ in range(n + 1)] for _ in range(n)]
    # table[j][k][s] = x[j+1]までからk枚選んで、その和がsの場合の数
    # 0 <= j < N, 0 <= k <= N, s <= sum(x)
    # jはインデックスだが,kは選ぶ枚数なので「j < n」「k < n + 1」
    # dp[j][k][s] = dp[j-1][k][s] # x[j]を選ばないとき
    #               + dp[j-1][k-1][s-x[j]] #x[j]を選ぶ場合 (ただし1<=j<=k)
    # dp[0][0][0] = 1 #初期値(シード的な)
    # dp = 0 # 上記以外の場合
    dp[0][0][0] = 1
    # j == 0 での処理
    dp[0][1][x[0]] = 1

    for j in range(len(dp)):
        for k in range(len(dp[0])):
            for s in range(len(dp[0][0])):
                # 「j == 0」での事前処理が必要
                if j > 0: # 解説では j > 0 and x[j] >= sらしい
                    dp[j][k][s] += dp[j-1][k][s]
                    if j > 0 and k > 0 and s >= x[j]:
                        dp[j][k][s] += dp[j-1][k-1][s-x[j]]
                        #print("dp[{}][{}][{}]:{} <- dp[{}][{}][{}]:{} + {}".format(
                            #j, k, s, dp[j][k][s], j-1, k-1, s-x[j], dp[j-1][k-1][s-x[j]], x[j]))
                # if dp[j][k][s] > 0:
                    # print("dp[{}][{}][{}]:{}---------------".format(j, k, s, dp[j][k][s]))
                # else:
                    # print("dp[{}][{}][{}]:{}".format(j, k, s, dp[j][k][s]))
    # for k in range(len(dp[0])):
        # for j in range(len(dp)):
            # print(dp[j][k])
    count = 0
    for k in range(1, min(len(dp[0]), len(dp[0][0]) // a + 1)):
            # print("dp[{}][{}][{}]:{}".format(n - 1, k, a * k, dp[n - 1][k][a * k]))
        count += dp[n-1][k][a*k]
    return count

n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
print(func(n, a, x))
"""
print(func(4, 8, [7, 8, 9, 9]))#合計33
print(func(3, 8, [6, 6, 9]))#合計21
print(func(8, 5, [3,6,2,8,7,6,5,9]))#合計46
print(func(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]))#合計46
"""

Submission status: Time Limit Exceeded

Solution code:
def func(n, a, x):
    x.sort()
    dp = [[[0 for _ in range(sum(x) + 1)] for _ in range(n + 1)] for _ in range(n)]
    # table[j][k][s] = x[j+1]までからk枚選んで、その和がsの場合の数
    # 0 <= j < N, 0 <= k <= N, s <= sum(x)
    # jはインデックスだが,kは選ぶ枚数なので「j < n」「k < n + 1」
    # dp[j][k][s] = dp[j-1][k][s] # x[j]を選ばないとき
    #               + dp[j-1][k-1][s-x[j]] #x[j]を選ぶ場合 (ただし1<=j<=k)
    # dp[0][0][0] = 1 #初期値(シード的な)
    # dp = 0 # 上記以外の場合
    dp[0][0][0] = 1
    dp[0][1][x[0]] = 1

    for j in range(len(dp)):
        for k in range(len(dp[0])):
            for s in range(len(dp[0][0])):
                # 「j == 0」での事前処理が必要
                if j > 0: # 解説では j > 0 and x[j] >= sらしい
                    dp[j][k][s] += dp[j-1][k][s]
                    if j > 0 and k > 0 and s >= x[j]:
                        dp[j][k][s] += dp[j-1][k-1][s-x[j]]
                        #print("dp[{}][{}][{}]:{} <- dp[{}][{}][{}]:{} + {}".format(
                            #j, k, s, dp[j][k][s], j-1, k-1, s-x[j], dp[j-1][k-1][s-x[j]], x[j]))
                # if dp[j][k][s] > 0:
                    # print("dp[{}][{}][{}]:{}---------------".format(j, k, s, dp[j][k][s]))
                # else:
                    # print("dp[{}][{}][{}]:{}".format(j, k, s, dp[j][k][s]))
    # for k in range(len(dp[0])):
        # for j in range(len(dp)):
            # print(dp[j][k])
    count = 0
    for k in range(len(dp[0])):
        if k > 0 and a*k <= len(dp[0][0]):
            # print("dp[{}][{}][{}]:{}".format(n - 1, k, a * k, dp[n - 1][k][a * k]))
            count += dp[n-1][k][a*k]
    return count

n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
print(func(n, a, x))
# print(func(4, 8, [7, 8, 9, 9]))#合計33
# print(func(3, 8, [6, 6, 9]))#合計21
# print(func(8, 5, [3,6,2,8,7,6,5,9]))#合計46
# print(func(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]))#合計46

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 enumerate(x, 1):
    for j in itertools.combinations(x, r=i):
        if sum(j) / i == A:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def generate_bin_list(num, target_list_len):
    flags = []
    for i in range(target_list_len):
        flags.append(0)
    b = list(bin(num))
    l_b = len(b)
    for j in range(0, l_b-2):
        flags[target_list_len-1-j] = int(b[l_b-1-j])
    return flags


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

length = pow(2, len(X))
cnt = 0
for i in range(1, length):
    flags = generate_bin_list(i, l_X)
    sum = 0
    for j in range(l_X):
        if flags[j] == 1:
            sum += X[j]
    if sum == 0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

flags = []
for i in range(l_X):
    flags.append(0)

length = pow(2, len(X))
cnt = 0
for i in range(1, length):
    b = list(bin(i))
    for j in range(l_X):
        flags[j] = 0
    l_b = len(b)
    for j in range(0, l_b-2):
        flags[l_X-1-j] = int(b[l_b-1-j])
    sum = 0
    for j in range(l_X):
        if flags[j] == 1:
            sum += X[j]
    if sum == 0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    N, A = li_input()
    X = sorted(li_input())
    ans = 0

    if N > 16:
        print("TLE")

    for i in range(1, 2**N):
        B = to_bin(i)
        B = "0" * (N - len(B)) + B

        s = 0
        m = 0
        for x,b in zip(X, B):
            if b == "1":
                s += x
                m += 1

        if s / m == A:
            ans += 1

    print(ans)
        


main()

Submission status: Time Limit Exceeded

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

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

xn_min_list = []

for i in range(1,N+1):
    num_list = []
    lsum = i*A
    for x in xn:
        if lsum < x:
            continue
        num_list.append(x)

    xn_min_list.append(num_list)

# print(xn_min_list)

ans = 0
for i, lst in enumerate(xn_min_list):
    lsum = (i+1)*A
    for c in itertools.combinations(lst, i+1):
        if sum(c) == lsum:
            ans += 1
            # print(list(c))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, A = map(int, input().split())
x = sorted([int(i)-A for i in input().split()])
ans = x.count(0)

if N >= 2:
    for i in range(2, N+1):
        check = list(itertools.combinations(x,i))
        for i in check:
            if sum(i) == 0:
                ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import combinations


def solve(N, A, Xs):
    diffs = [x - A for x in Xs]
    minus = [d for d in diffs if d < 0]
    minuses = []
    plus = [d for d in diffs if d > 0]
    pluses = []
    zero = [d for d in diffs if d == 0]

    for n in range(1, len(minus) + 1):
        for ns in combinations(minus, n):
            minuses.append(sum(ns))

    for n in range(1, len(plus) + 1):
        for ns in combinations(plus, n):
            pluses.append(sum(ns))

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

    z = sum([nCr(len(zero), r) for r in range(len(zero))])
    c = 0
    for m in minuses:
        c += pluses.count(-m) * (z + 1)
    c += z
    return c


if __name__ == "__main__":
    N, A = map(int, input().split(" "))
    Xs = map(int, input().split(" "))
    print(solve(N, A, Xs))

Submission status: Time Limit Exceeded

Solution code:
import itertools
def main():
    N, A = map(int, input().split())
    xi = list(map(int, input().split()))
    Answer = 0
    for i in range(1, len(xi)+1):
        for j in list(itertools.combinations(xi, i)):
            a = 0
            for w in j:
                a += w
            if a / i == A:
                Answer += 1
    print(Answer)


if __name__ == "__main__":
    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 i in range(1, N+1):
    check = list(itertools.combinations(x,i))
    for j in check:
        if sum(j) % len(j) == 0 and (sum(j) // len(j)) == A:
            ans +=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import statistics

n,a = [int(x) for x in stdin.readline().rstrip().split()]
x = [int(x) for x in stdin.readline().rstrip().split()]
ans = 0

for i in range(2**(n-1),2**n-1):
    list_1 = []
    list_0 = []
    s = format(i,"b")
    for j in range(len(s)):
        if s[j] == "1":
            list_1.append(x[j])
        else:
            list_0.append(x[j])
    if statistics.mean(list_1) == a:
        ans += 1
    if statistics.mean(list_0) == a:
        ans += 1
if statistics.mean(x) == a:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
iN,iA =[int(x) for x in input().split()]
#aX = [int(x) - iA for x in input().split()]
aX = [int(x) for x in input().split()]

#解法1
#すげーな動的計画法
iMX = max(aX + [iA])
dp = [[[0]*(iN*iMX + 1) for _ in range(iN+1)] for _ in range(iN + 1)]

dp[0][0][0] = 1
for j in range(1,iN+1):
    for k in range(0,iN+1):
        for s in range(0,iN*iMX + 1):
            if  s < aX[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif k >= 1 and  s >= aX[j-1]:
                dp[j][k][s] = dp[j-1][k][s]+dp[j-1][k-1][s- aX[j-1]]
            else:
                dp[j][k][s] = 0
iRet = 0
for k in range(1,iN+1):
    iRet += dp[iN][k][k*iA]
print(iRet)

Submission status: Time Limit Exceeded

Solution code:
iN,iA =[int(x) for x in input().split()]
#aX = [int(x) - iA for x in input().split()]
aX = [int(x) for x in input().split()]

#解法1を愚直にそのまま組んでみた
#すげーな動的計画法
iMX = max(aX + [iA])
dp = [[[0]*(iN*iMX + 1) for _ in range(iN+1)] for _ in range(iN + 1)]

for j in range(iN+1):
    for k in range(iN+1):
        for s in range(iN*iMX + 1):

            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif j >= 1 and s < aX[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif j >= 1 and k >= 1 and s >= aX[j-1]:
                dp[j][k][s] = dp[j-1][k][s]+dp[j-1][k-1][s- aX[j-1]]
            else:
                dp[j][k][s] = 0
iRet = 0
for k in range(1,iN+1):
    iRet += dp[iN][k][k*iA]
print(iRet)

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*A+1)] for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 1


for i in range(N):
    for j in range(N*A+1):
        for k in range(N):
 #i個の整数のうちk個使ってjにする場合の数
            if x[i] > j:
                dp[k][i+1][j] = dp[k][i][j]
            else:
                dp[k+1][i+1][j] = dp[k][i][j - x[i]] + dp[k+1][i][j]

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

Submission status: Time Limit Exceeded

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

def solve(N, A, x):
    x.append(0)
    x.sort()
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

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

def solve(N, A, x):
    x.append(0)
    x.sort()
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    print(solve(N, A, x))

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
from sys import stdin
input = stdin.readline
N,A=map(int, input().split())
x=[int(x) for x in input().split()]
x.append(0)
x.sort()
W=sum(x)
dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
    dp[j][0][0]=1
for j in range(1,N+1):
    xj=x[j]
    for k in range(1, N+1):
        for s in range(1, W+1):
            if s<xj:
                dp[j][k][s]=dp[j-1][k][s]
            else:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

ans=0
for k in range(1,N+1):
    if k*A<=W:
        ans+=dp[N][k][k*A]
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from sys import stdin
input = stdin.readline
N,A=map(int, input().split())
x=[int(x) for x in input().split()]
x.append(0)
x.sort()
W=sum(x)
dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
    dp[j][0][0]=1
for j in range(1,N+1):
    xj=x[j]
    for k in range(1, N+1):
        for s in range(1, W+1):
            if s<xj:
                dp[j][k][s]=dp[j-1][k][s]
            else:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

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

Submission status: Time Limit Exceeded

Solution code:
N,A=map(int, input().split())
x=[int(x) for x in input().split()]
x.append(0)
x.sort()
W=sum(x)
dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
    dp[j][0][0]=1
for j in range(1,N+1):
    xj=x[j]
    for k in range(1, N+1):
        for s in range(1, W+1):
            if s<xj:
                dp[j][k][s]=dp[j-1][k][s]
            else:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

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

Submission status: Time Limit Exceeded

Solution code:
N,A=map(int, input().split())
x=[int(x) for x in input().split()]
x.sort()
W=sum(x)
dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
    dp[j][0][0]=1
for j in range(1,N+1):
    xj=x[j-1]
    for k in range(1, N+1):
        for s in range(1, W+1):
            if s<xj:
                dp[j][k][s]=dp[j-1][k][s]
            else:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

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

Submission status: Time Limit Exceeded

Solution code:
N,A=map(int, input().split())
x=[int(x) for x in input().split()]
W=sum(x)
dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
    dp[j][0][0]=1
for j in range(1,N+1):
    xj=x[j-1]
    for k in range(1, N+1):
        for s in range(1, W+1):
            if s<xj:
                dp[j][k][s]=dp[j-1][k][s]
            else:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

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

Submission status: Time Limit Exceeded

Solution code:
N,A=map(int, input().split())
x=list(map(int, input().split()))
W=sum(x)
dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
    dp[j][0][0]=1
for j in range(1,N+1):
    xj=x[j-1]
    for k in range(1, N+1):
        for s in range(1, W+1):
            if s<xj:
                dp[j][k][s]=dp[j-1][k][s]
            else:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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