Problem:


Score : 300 points

Problem Statement

Tak has N cards. On the i-th (1 \leq i \leq N) card is written an integer x_i.
He is selecting one or more cards from these N cards, so that the average of the integers written on the selected cards is exactly A.
In how many ways can he make his selection?

Constraints

1 \leq N \leq 50

1 \leq A \leq 50

1 \leq x_i \leq 50

N,\,A,\,x_i are integers.

Partial Score

200 points will be awarded for passing the test set satisfying 1 \leq N \leq 16.

Input

The input is given from Standard Input in the following format:

N A
x_1 x_2 ... x_N

Output

Print the number of ways to select cards such that the average of the written integers is exactly A.

Sample Input 1

4 8
7 9 8 9

Sample Output 1

5

The following are the 5 ways to select cards such that the average is 8:

Select the 3-rd card.

Select the 1-st and 2-nd cards.

Select the 1-st and 4-th cards.

Select the 1-st, 2-nd and 3-rd cards.

Select the 1-st, 3-rd and 4-th cards.

Sample Input 2

3 8
6 6 9

Sample Output 2

0

Sample Input 3

8 5
3 6 2 8 7 6 5 9

Sample Output 3

19

Sample Input 4

33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

Sample Output 4

8589934591

The answer may not fit into a 32-bit integer.



Sample input:
4 8
7 9 8 9


Sample output:
5

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = xs[:l], r - l, xs[r:]
if len(low) > len(high):
    low, high = list(map(neg, high)), list(map(neg, low))
else:
    high = high[::-1]
acc = list(accumulate(high[::-1]))[::-1]

factor = 2 ** n0
lsums = Counter([0])
for v in low:
    tmps = tuple(lsums.items())
    for u, cnt in tmps:
        lsums[u + v] += cnt
del lsums[0]
ans = 0
for lsum, cnt in lsums.items():
    tmp = 0
    q = deque()
    q.append((0, lsum))
    while len(q) > 0:
        i, v = q.popleft()
        if i + 1 < len(high) and v + acc[i + 1] >= 0:
            q.append((i + 1, v))
        if i >= len(high):
            continue
        v += high[i]
        if v == 0:
            tmp += 1
            continue
        if v < 0:
            q.append((i + 1, v))
    ans += tmp * cnt

ans *= factor
ans += 2 ** n0 - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = xs[:l], r - l, xs[r:]
if len(low) > len(high):
    low, high = list(map(neg, high)), list(map(neg, low))
else:
    high = high[::-1]
acc = list(accumulate(high[::-1]))[::-1]

factor = 2 ** n0
lsums = sum((Counter(map(sum, combinations(low, 1 + i))) for i in range(len(low))), Counter())

ans = 0
for lsum, cnt in lsums.items():
    tmp = 0
    q = deque()
    q.append((0, lsum))
    while len(q) > 0:
        i, v = q.popleft()
        if i + 1 < len(high) and v + acc[i + 1] >= 0:
            q.append((i + 1, v))
        if i >= len(high):
            continue
        v += high[i]
        if v == 0:
            tmp += 1
            continue
        if v < 0:
            q.append((i + 1, v))
    ans += tmp * cnt

ans *= factor
ans += 2 ** n0 - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = xs[:l], r - l, xs[r:]
if len(low) > len(high):
    low, high = list(map(neg, high)), list(map(neg, low))
else:
    high = high[::-1]
acc = list(accumulate(high[::-1]))[::-1]
factor = 2 ** n0
lsums = sum((Counter(map(sum, combinations(low, 1 + i))) for i in range(len(low))), Counter())

ans = 0
for lsum, cnt in lsums.items():
    tmp = 0
    q = deque()
    q.append((0, lsum))
    while len(q) > 0:
        i, v = q.popleft()
        if i >= len(high):
            continue
        if v + acc[i] < 0:
            continue
        q.append((i + 1, v))
        v += high[i]
        if v == 0:
            tmp += 1
            continue
        if v > 0:
            continue
        q.append((i + 1, v))
    ans += tmp * cnt

ans *= factor
ans += 2 ** n0 - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import Counter
from itertools import combinations
from math import factorial
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = xs[:l], r - l, xs[r:]
if len(low) > len(high):
    low, high = high, low

factor = 2 ** n0
lsums = sum((Counter(map(sum, combinations(low, 1 + i))) for i in range(len(low))), Counter())
hsums = sum((Counter(map(sum, combinations(high, 1 + i))) for i in range(len(high))), Counter())

ans = 0
for lsum, cnt in lsums.items():
    ans += cnt * hsums[-lsum]
ans *= factor
if n0:
    ans += (2 ** n0 - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import Counter
from itertools import combinations
from math import factorial
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, zeros, high = xs[:l], xs[l:r], xs[r:]

factor = 2 ** len(zeros)
lsums = sum((Counter(map(sum, combinations(low, 1 + i))) for i in range(len(low))), Counter())
hsums = sum((Counter(map(sum, combinations(high, 1 + i))) for i in range(len(high))), Counter())

ans = 0
for lsum, cnt in lsums.items():
    ans += cnt * hsums[-lsum]
ans *= factor
if len(zeros):
    ans += (2 ** len(zeros) - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def inpl():
    return list(map(int, input().split()))


N, A = inpl()
X = inpl()
cX = Counter(X)

dp = [[[0 for _ in range(N * max(X) + 1)] for j in range(i + 1)]
      for i in range(N + 1)]

dp[0][0][0] = 1
for i in range(1, N + 1):
    x = X[i - 1]
    for j in range(i + 1):
        for k in range(N * max(X) + 1):
            # print(i, j, k)
            if j == i and k - x < 0:
                dp[i][j][k] = 0
            elif j == i and k - x >= 0:
                dp[i][j][k] = dp[i - 1][j - 1][k - x]
            elif k - x < 0 or j == 0:
                dp[i][j][k] = dp[i - 1][j][k]
            else:
                dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - x]

ans = 0
for j in range(1, N + 1):
    if j * A > N * max(X):
        continue
    ans += dp[N][j][j * A]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/2/16
Solved on 2019/2/
@author: shinjisu
"""


# ARC 060 C Tak and Cards
def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


def genBits(n):  # n個の0/1のリストを生成　[0]から変化
    bits = zeros(n)
    for i in range(2**n):
        for k in range(n):
            bits[k] = i % 2
            i //= 2
        yield bits


def dmp(x):
    global debug
    if debug:
        print(x)
    return x


def probC():
    N, A = getIntList()
    X = getIntList()
    dmp((N, A, X))
    cards = [a - A for a in X]
    dmp(cards)
    cards.sort()
    dmp(cards)
    #histogram = zeros(max(X)+1)
    #plusMinus = zeros2(max(X)+1, 2)
    #dmp(plusMinus)
    minus = []
    plus = []
    zero = 0
    for i in range(N):
        if cards[i] < 0:
            minus.append(cards[i])
        elif cards[i] > 0:
            plus.append(cards[i])
        else:
            zero += 1
    minus.reverse()
    dmp((minus, plus, zero))

    # マイナス部
    minusSum = {}
    for b in genBits(len(minus)):
        sm = 0
        for i in range(len(minus)):
            sm += minus[i]*b[i]
        if abs(sm) in minusSum:
            minusSum[abs(sm)] += 1
        else:
            minusSum[abs(sm)] = 1
    dmp(('minusSum',minusSum))

    # プラス部
    plusSum = {}
    for b in genBits(len(plus)):
        sm = 0
        for i in range(len(plus)):
            sm += plus[i]*b[i]
        if sm in plusSum:
            plusSum[sm] += 1
        else:
            plusSum[sm] = 1
    dmp(('plusSum',plusSum))

    # +と-の照合
    match = []
    for ms in minusSum: 
        if ms in plusSum and ms != 0:
            match.append([ms, minusSum[ms], plusSum[ms]])
    dmp(('match',match))
    # ゼロ
    count = 2**zero - 1  # Aだけ
    dmp(count)
    for mt in match:
        count += mt[1] * mt[2] * 2**zero
    return dmp(count)
"""
    zero = histogram[A]
    for i in range(1, len(histogram)):
        if A-i < 0 or A+i >= len(histogram):
            break
        plusMinus[i] = [histogram[A-i], histogram[A+i]]
    dmp(plusMinus)
"""
"""
    for i in range(len(plusMinus)):
        count += plusMinus[i][0] * plusMinus[i][1] * 2**zero
        dmp(count)
"""


debug = False  # True False
print(probC())


"""
# ARC 060 例3が解けない bitsの順が大きい順or小さい順にならないことがある
N,A = getIntList()
db((N,A))
x = getIntList()
db(x)
for i in range(N):
    x[i] -= A
x.sort()
db(x)
for i in range(N):
    if x[i]>=0:
        mn = i # 最後のマイナスの次
        break
for j in range(i,N):
    if x[j]>0:
        pl = j # 最初のプラス
        break
else: pl = N
zr = pl - mn # ゼロの数
minus = zeros(mn)
for i in range(mn): minus[i] = x[mn-1-i]
plus = zeros(N-pl)
for i in range(N-pl): plus[i] = x[pl+i]
db((mn,pl,zr));db(minus);db(plus)
pBits = genBits(N-pl)
pb = next(pBits)
pSum = 0
mnCnt = {}; plCnt = {}
try:
    for mb in genBits(mn):
        mSum = 0
        for i in range(mn): mSum += mb[i]*minus[i]
        db(('m',mb,mSum))
        while mSum+pSum<0:
            pSum = 0
            pb = next(pBits)
            for i in range(N-pl): pSum += pb[i]*plus[i]
            db(('p1',pb,pSum))
        while mSum+pSum==0:
            if mSum in mnCnt: mnCnt[mSum] += 1
            else: mnCnt[mSum] = 1
            if pSum in plCnt: plCnt[pSum] += 1
            else: plCnt[pSum] = 1
            pSum = 0
            pb = next(pBits)
            for i in range(N-pl): pSum += pb[i]*plus[i]
            db(('p2',pb,pSum))
        db((mnCnt,plCnt))
except StopIteration:
    pass
db((mnCnt,plCnt,zr))
db(2**zr-1)
cnt = 0
for k in plCnt.keys():
    cnt += mnCnt[-k]*plCnt[k]
cnt *= 2**zr-1
print(cnt)
"""

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
p=max(max(x),a)
s=[i-a for i in x]
def f(b,t):
    if b==0 and t==p*n:
        return 1
    elif b>0 and (t-s[b-1]<0 or t-s[b-1]>2*p*n):
        return f(b-1,t)
    elif b>0 and (0<=t-s[b-1] and t-s[b-1]<=2*p*n):
        return f(b-1,t)+f(b-1,t-s[b-1])
    else:
        return 0
print(f(n,n*p)-1)

Submission status: Time Limit Exceeded

Solution code:
def makelist(n,m,p):
    return [[[0 for k in range(p)]for i in range(m)]for j in range(n)]

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

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

Submission status: Time Limit Exceeded

Solution code:
def makelist(n,m,p):
    return [[[0 for k in range(p)]for i in range(m)]for j in range(n)]

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

dp = makelist(n+1,n+1,n*a+1)
dp[0][0][0] = 1
for j in range(n+1):
    for k in range(n+1):
        for s in range(n*a+1):
            if j*k > 0 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 >= 1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
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()))
ans = 0
for bit in range(2**n):
    x_sum = 0
    count = 0
    for j in range(n):
        if bit>>j&1:
            x_sum += x[j]
            count += 1
    if count > 0:
        if x_sum == a*count:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

na = n*a
DP = [[0]*(na+1) for i in range(n+1)]
DP[0][0] = 1

for _ in range(n):
    x = xs[_]
    next = [[0]*(na+1) for i in range(n+1)]
    for i in range(n):
        for j in range(na+1):
            # xを使わないとき
            next[i][j] += DP[i][j]
            if j+x <= na:
                next[i+1][j+x] += DP[i][j]
    DP = next

# i枚使ったとき合計がi*aである場合の数
ans = 0
for i in range(1,n+1):
    ans += DP[i][i*a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, A = (int(i) for i in input().split())
x = [int(i) for i in input().split()]
sumx = sum(x)
DP = [[[0] * (N+1) for i in range(sumx+1)] for i in range(N+1)]
DP[0][0][0] = 1
for i in range(N):
    for j in range(sumx+1):
        for k in range(i+1):
            if j - x[i] >= 0:
                DP[i+1][j][k+1] += DP[i][j-x[i]][k]
            DP[i+1][j][k] += DP[i][j][k]

res = 0
for i in range(1,N+1):
    if i * A <= sumx:
        res += DP[N][i * A][i]
print(res)

Submission status: Time Limit Exceeded

Solution code:
N, A = (int(i) for i in input().split())
x = [int(i) for i in input().split()]
sumx = sum(x)
DP = [[[0] * (N+1) for i in range(sumx+1)] for i in range(N+1)]
DP[0][0][0] = 1
for i in range(N):
    for j in range(sumx+1):
        for k in range(N):
            if j - x[i] >= 0:
                DP[i+1][j][k+1] += DP[i][j-x[i]][k]
            DP[i+1][j][k] += DP[i][j][k]

res = 0
for i in range(1,N+1):
    if i * A <= sumx:
        res += DP[N][i * A][i]
print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,A=map(int,input().split())
l=input().split()
ls=[]
a=0
s=1
for i in l:
     ls.append(eval(i))
def fn(ls,s):
     global a
     for i in itertools.combinations(ls,s):
          if sum(i)/s==A:
               a+=1
     if s<N:
          s+=1
          fn(ls,s)
     else:
          print(a)
fn(ls,s)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,A=map(int,input().split())
l=input().split()
ls=[]
a=0
for i in l:
     ls.append(eval(i))
for s in range(1,N+1):
     for i in itertools.combinations(ls,s):
          if sum(i)/s==A:
               a+=1
print(a)

Submission status: Time Limit Exceeded

Solution code:
n,a,*x=map(int,open(0).read().split())
x=[0]+x
dp=[[[0]*(50*n+1)for j in range(n+1)]for i in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  dp[i][0]=dp[i-1][0]
  for j in range(1,n+1):
    for k in range(1,50*n+1):
      dp[i][j][k]=dp[i-1][j][k]
      if k-x[i]>=0:
        dp[i][j][k]+=dp[i-1][j-1][k-x[i]]
ans=0
for i in range(1,n+1):
  j=i*a
  if j<50*n+2:
    ans+=dp[-1][i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a = (int(i) for i in input().split())
x = list(int(i) for i in input().split())
count = 0
for i in x:
    if i == 8:
        count+=1
res = 0
for i in range(1,2**n):
    bit = bin(i)[2:]
    k = bit.count("1")
    sum = 0
    for i in range(1,len(bit)+1):
        if bit[-i]=="1":
            sum += x[-i]
    if sum==a*k:
        res += 1

print(res)

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
lis = []
for i in range(2**n):
    d = list(map(int, list(bin(i))[2:]))
    while len(d) < n:
        d.insert(0,0)
    lis.append(d)
ans = -1
for i in lis:
    su = 0
    for j in range(n):
        su += i[j]*x[j]
    if su == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

dp = [[[0 for i in range(N+1)] for j in range(N)] for k in range(2501)]
dp[0][0][0] = 1
dp[x[0]][0][1] = 1
for i in range(N-1):
    for j in range(N*A+1):
        if j-x[i+1]>=0:
            for k in range(0,N+1):
                if k!=0:
                    dp[j][i+1][k]=dp[j-x[i+1]][i][k-1]+dp[j][i][k]
                else:
                    dp[j][i+1][k]=dp[j][i][k]
        else:
            for k in range(0,N+1):
                dp[j][i+1][k]=dp[j][i][k]
score = 0

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

print(score)

Submission status: Time Limit Exceeded

Solution code:
n,a = map(int, input().split())
list_x = list(map(int, input().split()))
dp = [ [[0] * 2600 for i in range(100)] for j in range(100)]
for j in range(n+1):
	for k in range(n+1):
		for s in range(sum(list_x) + 1):
			if j == 0 and k == 0 and s == 0:
				dp[j][k][s] = 1
			elif j >= 1 and s < list_x[j - 1]:
				dp[j][k][s] = dp[j - 1][k][s]
			elif j >= 1 and k >= 1 and s >= list_x[j - 1]:
				dp[j][k][s] = dp[j - 1][k - 1][s - list_x[j-1]] + dp[j - 1][k][s]
			else:
				dp[j][k][s] = 0
ans = 0
for p in range(1,n+1):
	ans += dp[n][p][p*a]
print(ans)

Submission status: Time Limit Exceeded

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

MAX = 2501

x = sorted(x)

z = 0
p = []
m = []
for i in range(n):
    x[i] -= a
    if x[i] == 0:
        z += 1
    elif x[i] > 0:
        p.append(x[i])
    else:
        m.append(-1 * x[i])

plus = [0 for _ in range(MAX)]
#minus = [0 for _ in range(MAX)]

ans = 2 ** z - 1

#print(p, m, z)

def calc_plus(temp_sum, i):
    if i >= len(p):
        plus[temp_sum] += 1
        return
    else:
        calc_plus(temp_sum, i + 1)
        calc_plus(temp_sum + p[i], i + 1)

calc_plus(0,0)

#print(plus)

def calc_minus(temp_sum, i):
    if i >= len(m):
        if temp_sum > 0 and plus[temp_sum] > 0:
            global ans
            ans += plus[temp_sum] * (2 ** z)
        return
    else:
        calc_minus(temp_sum, i + 1)
        calc_minus(temp_sum + m[i], i + 1)


calc_minus(0,0)

print(ans)

Submission status: Time Limit Exceeded

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

x = sorted(x)

ans = 0
for i in range(n):
    x[i] -= a
    if x[i] == 0:
        ans += 1

if x[0] >= 0 or x[n - 1] <= 0:
    print(2 ** ans - 1)
    exit()

ans = 0

def adder(temp_sum, i):
    if i >= n:
        return
    else:
        if temp_sum + x[i] == 0:
            global ans
            ans += 1
        adder(temp_sum, i + 1)
        adder(temp_sum + x[i], i + 1)

adder(0,0)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
line = input().split(" ")
n = int(line[0])
a = int(line[1])
x = [int(i) for i in input().split(" ")]

X = max(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>0 and s<x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif j>0 and k>0 and s>=x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]

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

Submission status: Time Limit Exceeded

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

xa = []
xb = []
count = 0
for i in x:
    if i > a:
        xa.append(i-a)
    elif i < a:
        xb.append(i-a)
    else:
        count += 1
ans = 0
if len(xa) == 0 or len(xb) == 0:
    print(2**count-1)
else:
    for i in range(1,len(xa)+1):
        for j in range(1,len(xb)+1):
            for k in itertools.combinations(xa,i):
                for l in itertools.combinations(xb,j):
                    if sum(k)+sum(l) == 0:
                        ans += 1
    if ans == 0:
        print(0)
    elif count == 0:
        print(ans)
    else:
        print((ans+1)*2**count-count)

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
s=n*a
dp=[[[0 for i in range(s+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(i+2):
    for k in range(s+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]
outp=0
for i in range(1,n+1):
  outp+=dp[n][i][i*a]
print(outp)

Submission status: Time Limit Exceeded

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

dp = [[[0 for _ in range(2501)] for _ in range(N + 1)] for _ in range(N + 1)]

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

for i in range(N):
    for a in range(N):
        for p in range(2500 - x[i]):
            dp[i + 1][a + 1][p + x[i]] += dp[i][a][p]
            dp[i + 1][a][p] += dp[i][a][p]


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

print(ret)

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(50*50)] for j in range(N+1) ]for k in range(N+1)]
dp[0][0][0]=1
for i in range(1,N+1):
  for j in range(N+1):
    for k in range(50*50):
      dp[i][j][k]=dp[i-1][j][k]
      if x[i-1]<= k and j>0: dp[i][j][k]+=dp[i-1][j-1][k-x[i-1]]
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 = [int(i) for i in input().split()]
x = [0]
for i in input().split():
    x.append(int(i))

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

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

print(sum)

Submission status: Time Limit Exceeded

Solution code:
n,a=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0 for _ in range(50*n+1)] for j in range(n+1)] for _ in range(n+1)] #dp[n][n][n*50]=cnt
dp[0][0][0] = 1
for i in range(1, n+1):
    for j in range(i+1):
        for k in range(50*n+1):
            if i > 0:
                dp[i][j][k] = dp[i-1][j][k]
                if k >= x[i-1]:
                    dp[i][j][k] += dp[i-1][j-1][k-x[i-1]]

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, A = map(int, raw_input().split())
x_n = map(int, raw_input().split())

ans_list = []
for i in xrange(1, len(x_n)+1):
    for x in itertools.combinations(x_n, i):
        if sum(x) / len(x) == A and sum(x) % len(x) == 0:
            ans_list.append(x)

print len(ans_list)

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):
    c = map(sum,itertools.combinations(x,i))
    cnt = list(c).count(i*A)
    ans += cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def makelist(n, m, p):
	return [[[0 for k in range(p)] for i in range(m)] for j in range(n)]

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

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

ans = 0
for 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, raw_input().split())
x = sorted(map(int, raw_input().split()))

def solve(n):
    mem = {}
    def rec(i, a, d):
        if (i, a, d) in mem:
            return mem[(i, a, d)]
        if i >= N:
            return 0
        if a < x[i]:
            return 0
        if d > n:
            return 0
        if x[i] == a and d == n-1:
            mem[(i, a, d)] = rec(i+1, a, d) + 1
        else:
            mem[(i, a, d)] = rec(i+1, a, d) + rec(i+1, a-x[i], d+1)
        return mem[(i, a, d)]
    return rec(0, n*A, 0)

s = 0
for i in xrange(1, N+1):
    s += solve(i)
print s

Submission status: Time Limit Exceeded

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

def search(xs, i=0, m=0):
    if len(xs) == 0:
        if i==A*m and m>0:
            return 1
        else:
            return 0
    else:
        return search(xs[1:], i+xs[0], m+1)  + search(xs[1:], i, m)


print(search(xs))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
from itertools import permutations as perms

def main():
	[n, a]=list(map(int, (stdin.readline()).rstrip().split(' ')))
	input=list(map(int, (stdin.readline().rstrip()).split(' ')))
	dp = [[[0 for _ in range(0, 2553)] for _ in range(0, 52)] for _ in  range(0, 52)]

	for i in range(0, n+1):
		dp[i][0][0]=1
	#take each
	for i in range(1, n+1):
		el=input[i-1]
		#how many we use from last i elems
		for j in range(1, i+1):
			# each sum
			for s in range(0, 2553-52):
				dp[i][j][s]+=dp[i-1][j][s]
				dp[i][j][s+el]+=dp[i-1][j-1][s]
	ans=0
	for i in range(1, len(dp[n])):
		ans+=dp[n][i][i*a]
	print(ans)

if __name__=='__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, K = list(map(int, input().split()))
x = list(map(int, input().split()))
count = 0

for i in range(N):
    p = itertools.combinations(x,i+1)
    p_ave = [sum(j)/(i+1) for j in p]
    count += len(list(filter(lambda n:n==K, p_ave)))
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

ans = 0

N, A = map(int, raw_input().split())

x = map(int, raw_input().split())

for i in range(N):
  for element in itertools.combinations(x, i + 1):
    if sum(element) / (i + 1.0) == A:
      ans += 1

print ans

Submission status: Time Limit Exceeded

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


def f(arr, allsum, selnum):
    if len(arr) == selnum:
        return 1 if sum(arr) == allsum else 0
    if selnum == 1:
        return arr.count(allsum)
    return f(arr[0:-1], allsum - arr[-1], selnum - 1) + f(arr[0:-1], allsum, selnum)

if __name__ == "__main__":
    result = 0
    for i in range(1, n + 1):
        result += f(x, a * i, i)
    print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def enum(n,x,A):
	D = defaultdict(int)
	D[0] = 1
	L = [None]*(1<<n)
	L[0] = 0
	for k in xrange(1<<n):
		for j in xrange(n):
			jbit = 1<<j
			if (k&jbit): continue
			nbit = k + jbit
			if L[nbit] is None: 
				nv = L[k] + x[j]
				L[nbit] = nv
				cnt = bin(nbit).count("1")
				D[nv-A*cnt] += 1
	return D
def solve():
	N,A = map(int,raw_input().split())
	x = map(int,raw_input().split())
	n1 = N/2; n2 = N - n1
	D1 = enum(n1,x[:n1],A)
	D2 = enum(n2,x[n1:],A)
	ans = 0
	for k,v in D1.iteritems():
		ans += D2[-k]*v
	print ans - 1
solve()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, K = list(map(int, input().split()))
x = list(map(int, input().split()))
count = 0

for i in range(N):
    p = itertools.combinations(x,i+1)
    for j in p:
        if K == (sum(j)/(i+1)):
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

import array
import statistics


EPS = 1e-9
MAX_N = 16


def isclose(x, y, tol=EPS):
    return abs(x - y) <= EPS


def count_combinations(n, a, xs):
    ans = 0
    for s in range(1, 1 << n):
        m = statistics.mean(xs[i] for i in range(n) if s & (1 << i))
        if isclose(a, m):
            ans += 1
    return ans


def main():
    n, a = map(int, input().split())
    assert n <= 16
    xs = array.array("I", map(int, input().split()))
    print(count_combinations(n, a, xs))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n,a = ii()
x = ii()
ans=0

def dp(i,b,c):
    if i<0:
        return 0
    elif b>i+1:
        return 0
    elif b==1:
        return x[0:i+1].count(c)
    else:
        return dp(i-1,b,c)+dp(i-1,b-1,c-x[i])
        
for j in range(n):
    ans+=dp(n-1,j+1,a*(j+1))

print ans

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n,a = map(int , raw_input().split())
har = map(int , raw_input().split())
ans = 0
for i in xrange(1,n+1):
    for ix in combinations(har,i):
        if sum(list(ix))/float(i) == a:
            ans += 1
print ans

Submission status: Accepted

Solution code:
N,A = map(int,input().split())
x = list(map(int,input().split()))
dp = [[[0]*(N*50+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1
#print(dp[0])

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

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