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: Runtime Error

Solution code:
def dp(k, value):
    if k==n:
        if value==0:
            return 1
        else:
            return 0
    if memo[k][value]>=0:
        return memo[k][value]
    memo[k][value]=dp(k+1, value+x[k])+dp(k+1, value)
    return memo[k][value]
print(dp(0, 0)-1)

Submission status: Runtime Error

Solution code:
n, a =map(int, input().split())
x=list(map(int, input().split()))
x=[i-a for i in x]
memo=[[-1]*110 for i in range(60)]
def dp(k, value):
    if k==n:
        if value==0:
            return 1
        else:
            return 0
    if memo[k][value]>0:
        return memo[k][value]
    memo[k][value]=dp(k+1, value+x[k])+dp(k+1, value)
    return memo[k][value]
print(dp(0, 0)-1)

Submission status: Runtime Error

Solution code:
n, a =map(int, input().split())
x=list(map(int, input().split()))
x=[i-a for i in x]
memo=[[-1]*110 for i in range(60)]
def dp(k, value):
    if k==n:
        if value==0:
            return 1
        else:
            return 0
    if memo[k][value]>0:
        return memo[k][value]
    memo[k][value]=dp(k+1, value+x[k])+dp(k+1, value)
    print(memo[k][value], k, value)
    return memo[k][value]
print(dp(0, 0)-1)

Submission status: Runtime Error

Solution code:
import numpy as np
hi = np.zeros((5000,60),np.int64)
hi[0,0]=1
n,a = [int(it) for it in input().split()]
li = [int(it) for it in input().split()]
for i in li:
  　hi_ = hi.copy()
    hi[i:-1,1:]+=hi_[:-1-i,:-1]
s = 0
for i in range(n):
  s+=hi[(i+1)*a,i+1]
print (s)

Submission status: Runtime Error

Solution code:
import itertools
import math 

n,s = [int(input()) for _ in range(2)]

def n_base_sum(n,b):
    if(int(n/b)):
        return n_base_sum(int(n/b),b)+n%b
    else:
        return n%b

def search_p(n,s):
    for p in range(math.ceil(math.sqrt(n))+1,0,-1):
        b = (n-s)//p + 1
        q = n - p*b
        if p+q ==s and b !=0:
            return b
    return -1

ans =-1
flag = False
answers = []
if s == n:
    ans = n+1
    flag =True
    answers.append(ans)
for b in  range(2,math.ceil(math.sqrt(n))+1):
    if s== n_base_sum(n,b):
        ans = b
        flag = True
        answers.append(ans)
        break
ans = search_p(n,s)
if ans != -1:
    flag =True
    answers.append(ans)


if not flag:
    print(-1)
else:
    print(int(min(answers)))

Submission status: Runtime Error

Solution code:
n,a=map(int, input().split())
x=list(map(int, input().split()))
x=[i-a for i in x]
d={0:1}
for i in x:
    for j,k in list(d.items()):
        d[i+.j]=d.get(i+j,0)+k
print(d[0]-1)
#sample code

Submission status: Runtime Error

Solution code:
N,A = map(int, input().split())
x = list(map(int, input().split()))
assert(1<=N<=16)
ans = 0
for i in range(2**N):
    # print(bin(i))
    s = 0
    cnt = 0
    for keta in range(N):
        if (i>>keta)%2==1:
            s += x[keta]
            cnt += 1 
    if cnt==0: continue
    if s/cnt==A:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N,A = map(int,input().split())
X = [0]+list(map(int,input().split()))
dp = []
for i in range(N+1):
  K = []
  for j in range(N+1):
    J = [0]*(N*max(X)+1)
    K.append(J)
  dp.append(K)
for j in range(N+1):
  for k in range(N+1):
    for s in range(N*max(X)+1):
      if j >= 1:
        if s < X[j]:
          dp[j][k][s] = dp[j-1][k][s]
        elif s >= X[j] and k >= 1:
          dp[j][k][s] = dp[j-1][k][s]+dp[j-1][k-1][s-X[j]]
        else:
          dp[j][k][s] = 0
      else:
        if k == 0 and s == 0:
          dp[j][k][s] = 1
        else:
          dp[j][k][s] = 0
ans = 0
for i in range(1,N+1):
  ans += dp[N][i][i*A]
print(ans)

Submission status: Runtime Error

Solution code:
N,A = map(int,input().split())
X = [0]+list(map(int,input().split()))
dp = []
for i in range(N+1):
  K = []
  for j in range(N+1):
    J = [0]*(N*max(X)+1)
    K.append(J)
  dp.append(K)
for j in range(N+1):
  for k in range(N+1):
    for s in range(N*max(X)+1):
      if j >= 1:
        if s < X[j]:
          dp[j][k][s] = dp[j-1][k][s]
        elif s >= X[j] and k >= 1:
          dp[j][k][s] = dp[j-1][k][s]+dp[j-1][k-1][s-X[j]]
        else:
          dp[j][k][s] = 0
      else:
        if k == 0 and s == 0:
          dp[j][k][s] = 1
        else:
          dp[j][k][s] = 0
ans = 0
for i in range(N):
  ans += dp[N][i][i*A]
print(ans)

Submission status: Runtime Error

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]
print(sum(dp[N][j][j * A] for j in range(1, N + 1)))

Submission status: Runtime Error

Solution code:
def inpl(): return [int(i) for i in input().split()]
def hmd(a, b):
    ctr = -1
    while H[ctr+1][a] < b:
        ctr += 1
    vn = H[ctr][a]
    if (vn == b and ctr == 0) or ctr == -1:
        return 1
    return 2**ctr + hmd(vn,b)
N = int(input())
x = inpl() + [10**10]
L = int(input())
H = []
G = [N-1]*N
b = 0
for a in range(N):
    while x[b+1] - x[a] <= L:
        if b == N-1:
            break
        b += 1
    G[a] = b
H.append(G)
while G[0] != N-1:
    G = [G[i] for i in G]
    H.append(G)
H.append([10**10]*N)
Q = int(input())
for _ in range(Q):
    a, b = sorted(inpl())
    print(hmd(a-1,b-1))

Submission status: Runtime Error

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(N*A+1)]
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: Runtime Error

Solution code:
def digit_sum(n, s):
    if s > n:
        return -1
    if s == n:
        return n + 1

    b = 2
    while b**2 < n:
        if f(b, n) == s:
            return b

        b += 1

    p = int(n * 0.5)
    while p > 1:
        b = (n - s) // p + 1
        if b > 1 and f(b, n) == s:
            return b
        
        p -= 1

    return -1


def f(b, n):
    if n < b:
        return n

    return f(b, n // b) + (n % b)

def solve():
    n = int(input())
    s = int(input())
    result = digit_sum(n, s)
    print(result)

solve()

Submission status: Runtime Error

Solution code:
def digit_sum(n, s):
    if s > n:
        return -1
    if s == n:
        return n + 1

    b = 2
    while b**2 < n:
        if f(b, n) == s:
            return b

        b += 1

    p = 1
    while p**2 < n:
        b = (n - s) // p + 1
        if b <= 1:
            break

        if f(b, n) == s:
            return b
        
        p += 1

    return -1


def f(b, n):
    if n < b:
        return n

    return f(b, n // b) + (n % b)

def solve():
    n = int(input())
    s = int(input())
    result = digit_sum(n, s)
    print(result)

solve()

Submission status: Runtime Error

Solution code:
n,a = map(int, input().split())
list_x = list(map(int, input().split()))
dp = [ [[0] * (sum(list_x) + 1) for i 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(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: Runtime Error

Solution code:
n,a = map(int, input().split())
list_x = list(map(int, input().split()))
dp = [ [[0] * 100 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: Runtime Error

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
xx = inpl()
L = int(input())

K = N.bit_length()
db_r = [[0]*K for i in range(N)]
for i,x in enumerate(xx):
    ind = bisect.bisect_right(xx,x+L)
    db_r[i][0] = ind-1

for k in range(1,K):
    for i in range(N):
        db_r[i][k] = db_r[db_r[i][k-1]][k-1]

def check(a,b,d):
    L = d.bit_length()
    for k in range(L):
        if d & (1<<k):
            a = db_r[a][k]
    return a >= b

Q = int(input())
for i in range(Q):
    a,b = inpl()
    a -= 1
    b -= 1
    a,b = min(a,b),max(a,b)
    OK = N
    NG = 0
    while OK-NG>1:
        mid = (OK+NG)//2
        if check(a,b,mid): OK = mid
        else: NG = mid
    print(OK)

Submission status: Runtime Error

Solution code:
N,A=map(int,input().split())
a=list(map(int, input().split()))
def hiku(kazu):
    return kazu-A
b=[]
for i in range(N):
    b.append(hiku(a[i]))
X=max(a)
def hai(s,t):
    if s==0 and t==NX:
        return 1
    elif s>=1 and (t-b[s]<0 or t-b[s]>2NX):
        return hai(s-1,t)
    elif s>=1 and (0<=t-b[s]<=2NX):
        return hai(s-1,t)+hai(s-1,t-b[s])
    else:
        return 0
print(hai(N,NX)-1)

Submission status: Runtime Error

Solution code:
n, a = list(map(int, input().split()))
x = list(map(int, input().split()))
dp = [[[0 for _ in range(n*max(x)+1)] for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1

for j in range(1, n+1):
  for k in range(n+1):
    for s in range(n*max(x)+1):
      if s<x[j-1]:
        dp[j][k][s] = dp[j-1][k][s]
      elif k>=1:
        dp[j][k][s] = dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]
ans = 0
for i in range(1, n+1):
  ans += dp[n][i][i*a]
print(ans)

Submission status: Runtime Error

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
x.insert(0,0)
xmax = max(x)
table = [[[0 for s in range(n*xmax+1)]for k in range(n+1)]for j in range(n+1)]
table[0][0][0] = 1
for s in range(n*xmax+1):
	for k in range(n+1):
		for j in range(1,n+1):
			if s < x[j]:
				table[j][k][s] = table[j-1][k][s]
			elif k>=1 and s>=x[j]:
				table[j][k][s] = table[j-1][k][s] + table[j-1][k-1][s-x[j]]
			else:
				table[j][k][s] = 0
total = 0
for i in range(1,n+1):
	total += table[n][i][i*a]
print(total)

Submission status: Runtime Error

Solution code:
n,a = map(int,input().split())
x = list(map(int,input().split()))
x.insert(0,0)
xmax = max(x)
table = [[[0 for s in range(n*xmax+1)]for k in range(n+1)]for j in range(n+1)]
table[0][0][0] = 1
for s in range(n*xmax+1):
	for k in range(n+1):
		for j in range(1,n+1):
			if s < x[j]:
				table[j][k][s] = table[j-1][k][s]
			elif k>=1 and s>=x[j]:
				table[j][k][s] = table[j-1][k][s] + table[j-1][k-1][s-x[j]]
			else:
				table[j][k][s] = 0
total = 0
for i in range(n):
	total += table[n][i][i*a]
print(total-1)

Submission status: Runtime Error

Solution code:
n = int(raw_input())
s = int(raw_input())

if n < s:
    print -1
elif s == 1:
    print n
else:
    ans_list = []
    for i in xrange(n/2, 1, -1):
        tmp_n = n
        total = 0
        while tmp_n / i > 0:
            total += tmp_n % i
            tmp_n /= i
        total += tmp_n

        print i, total
        if total == s:
            ans_list.append(i)

    print ans_list[len(ans_list)-1] if ans_list else -1

Submission status: Runtime Error

Solution code:
n,a=map(int,input().split())
x=[0]+[i-a for i in map(int,input().split())]
d={}
def f(i):
    if i==n+1:
        return c([0])
    if i in d:
        return d[i]
    d[i]={}
    for j in range(i+1,n+2):
        for k,v in f(j).items():
            d[i].setdefault(x[i]+k,0)
            d[i][x[i]+k]+=v
    return d[i]
print(f(0)[0]-1)

Submission status: Runtime Error

Solution code:
n = int(raw_input())
har = map(int , raw_input().split())
L = int(raw_input())
q = int(raw_input())

from collections import deque

def bfs(g, start):
    queue, enqueued = deque([(None, start)]), set([start])
    while queue:
        parent, n = queue.popleft()
        yield parent, n
        new = set(g[n]) - enqueued
        enqueued |= new
        queue.extend([(n, child) for child in new])
 
 
def s_p(g, start, end):
    parents = {}
    for parent, child in bfs(g, start):
        parents[child] = parent
        if child == end:
            revpath = [end]
            while True:
                parent = parents[child]
                revpath.append(parent)
                if parent == start:
                    break
                child = parent
            return list(reversed(revpath))
    return None # or raise appropriate exception

graph = {i:[] for i in xrange(n)}
for i in xrange(n):
    if i - 1 >= 0:graph[i].append(i-1)
    if i + 1 <= n-1:graph[i].append(i+1)
for i in xrange(q):
    a,b = map(int , raw_input().split())
    a-=1
    b-=1
    path = s_p(graph,a,b)
    ans = 0
    sm = 0
    #print path
    pre = har[path[0]]
    psm = 0
    cost = []
    pp = 0
    for ix in xrange(1,len(path)):
        sm += abs(har[path[ix]] - pre)
        psm += abs(har[path[ix]] - pre)
        pre = har[path[ix]]
        if sm > L:
          ans += 1
          sm -= pp
        if sm == L:
          sm = 0
          ans += 1
        cost.append(sm)
        pp = sm
    if sm > 0:
        ans += 1
    print ans

Submission status: Runtime Error

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 for j in p]
    count += len(list(filter(lambda n:n==K, p_ave)))
print(count)

Submission status: Runtime Error

Solution code:

line1=input().split()
n=int(line1[0])
a=int(line1[1])
nums=input().split()
for i in range(n):
    nums[i]=int(nums[i])-a

works={}

print (works)
s=0
for x in nums:

    if x>=0:
        for i in range(50*n,-50*n, -1):
            try:
                works[i]+=works[i-x]
            except:
                try:
                    works[i]=works[i-x]
                except:
                    pass
    else:
        for i in range (-50*n,50*n):
            try:
                works[i+x]+=works[i]
            except:
                try:
                    works[i+x]=works[i]
                except:
                    pass

print (works[0]-1)

Submission status: Runtime Error

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

EPS = 1e-9
MAX_N = 16


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


def mean(xs):
    n = len(xs)
    return sum(xs) / n


def count_combinations(n, a, xs):
    ans = 0
    for s in range(1, 1 << n):
        m = 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 = list(map(int, input().split()))
    print(count_combinations(n, a, xs))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

import array
import math
import statistics


MAX_N = 16


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 math.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: Runtime Error

Solution code:
from sys import exit

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

(N, A) = reads()
x = reads()

assert(N <= 16)

count = 0

for b in range(1, 1<<N):
  bits = [bool(b&(1 << i)) for i in range(N)]
  if sum(x[i] for i in range(N) if bits[i]) == A * sum(bits):
    count += 1
    # print(bits)

print(count)