Problem:


カードの組み合わせ

整数が書いてあるカードが何枚か入っている袋を使ってゲームをしましょう。各回のゲームで参加者はまず、好きな数 n を一つ宣言します。そして、袋の中から適当な枚数だけカードを一度に取り出して、それらのカードに書かれた数の総和が n に等しければ豪華賞品がもらえます。なお、それぞれのゲーム終了後カードは袋に戻されます。

袋の中の m 種類のカードの情報および、g 回のゲームで参加者が宣言した数を入力とし、それぞれのゲームで豪華商品をもらえるカードの組み合わせが何通りあるかを出力するプログラムを作成してください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。
各データセットは以下の形式で与えられます。

m
a1 b1
a2 b2
:
am bm
g
n1
n2
:
ng

１行目にカードの種類数 m （1 ≤ m ≤ 7）、続く m 行に i 種類目のカードに書かれた整数 ai (1 ≤ ai ≤ 100) とその枚数 bi (1 ≤ bi ≤ 10) が空白区切りで与えられます。

続く行にゲームの回数 g (1 ≤ g ≤ 10)、続く g 行にゲーム i で宣言された整数 ni (1 ≤ ni ≤ 1,000) が与えられます。

データセットの数は 100 を超えない。

Output

入力データセットごとに、i 行目にゲーム i で豪華賞品がもらえるカードの組み合わせ数を出力します。

Sample Input

5
1 10
5 3
10 3
25 2
50 2
4
120
500
100
168
7
1 10
3 10
5 10
10 10
25 10
50 10
100 10
3
452
574
787
0

Output for the Sample Input

16
0
12
7
9789
13658
17466



Sample input:
5
1 10
5 3
10 3
25 2
50 2
4
120
500
100
168
7
1 10
3 10
5 10
10 10
25 10
50 10
100 10
3
452
574
787
0


Sample output:
16
0
12
7
9789
13658
17466

Submission status: Wrong Answer

Solution code:
def f(i):
    global soc, ans, ng
    for n in range(m[i][1]+1):
        soc += (m[i][0]*n)
        if ng < soc:
            soc -= m[i][0]*n
            return
        elif ng == soc:
            ans += 1
            soc -= m[i][0]*n
            return
        elif i < len(m)-1:
            f(i+1)
        soc -= m[i][0]*n

m = [map(int, raw_input().split()) for i in range(input())]
g = [int(raw_input()) for i in range(input())]
soc = 0
ans = 0
for ng in g:
    f(0)
    print ans
    ans = 0
    soc = 0

Submission status: Memory Limit Exceeded

Solution code:
from itertools import combinations as C
while True:
    m = int(input())
    if m==0:break
    card = []
    total = 0
    for _ in range(m):
        a, b = map(int, input().split())
        card += [a]*b
        total += b

    g = int(input())
    for _ in range(g):
        ans = 0
        duplicate = []
        n = int(input())
        for i in range(1, total+1):
            for l in list(C(card, i)):
                if sum(l)==n and not l in duplicate:
                    ans += 1
                    duplicate.append(l)
        print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
ans = []
while 1:
    M = int(readline())
    if M == 0:
        break
    P = [list(map(int, input().split())) for i in range(M)]
    memo = {}
    def dfs(i, rest):
        if i == M:
            return rest == 0
        key = (i, rest)
        if key in memo:
            return memo[key]
        res = 0
        a, b = P[i]
        for j in range(0, b+1):
            if rest - j*a < 0:
                break
            res += dfs(i+1, rest - j*a)
        memo[key] = res
        return res
    G = int(input())
    for i in range(G):
        ans.append(str(dfs(0, int(input()))))
write("\n".join(ans))
write("\n")

Submission status: Accepted

Solution code:
while 1:
  m = int(raw_input())
  if m==0: break

  card = []
  total = 0
  for i in range(m):
    a, b = map(int, raw_input().split())
    card.append([a, b])
    total += a*b
  card = sorted(card)[::-1]

  B = [0]*(total+1)
  for a, b in card:
    A = B[:]
    B = [0] * (total+1)
    B[a:a*b+1:a] = [1]*b
    for i in range(total+1)[::-1]:
      if A[i]:
        for e in range(i, i+a*b+1, a):
          B[e] += A[i]

  g = int(raw_input())
  for _ in [0] * g:
    n = int(raw_input())
    if 0<=n<=total:
      print B[n]
    else:
      print 0

Submission status: Accepted

Solution code:
def In(): return int(raw_input())
while 1:
  m = In()
  if m==0: break

  card = [0]*m
  total = 0
  for i in range(m):
    a,b = map(int, raw_input().split())
    card[i] = [a,b]
    total += a*b
  card = sorted(card)[::-1]

  B = [0]*(total+1)
  for a,b in card:
    A = B[:]
    B = [0]*(total+1)
    B[a:a*b+1:a] = [1]*b
    for i in range(total+1)[::-1]:
      if A[i]:
        for e in range(i,i+a*b+1,a): B[e] += A[i]

  for _ in [0]*In():
    n = In()
    if 0<=n<=total: print B[n]
    else: print 0

Submission status: Accepted

Solution code:
while 1:
    n=int(input())
    if n==0:break
    dp=[1]+[0]*3000
    for i in range(n):
        a,b=map(int,input().split())
        for j in range(1001,-1,-1):
            for k in range(1,b+1):
                dp[j+a*k]+=dp[j]
    for _ in range(int(input())):
        print(dp[int(input())])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0154

"""
import sys
from sys import stdin
input = stdin.readline


def solve(m, cards, g, guesses):
    ans = []

    cards.append([0, 0])
    cards.sort()
    W = max(guesses) + 1

    dp = [0] * W
    dp[0] = 1
    for i in range(1, m+1):
        card_num = cards[i][0]
        card_rem = cards[i][1]
        for j in range(W-1, 0, -1):
            for k in range(1, card_rem+1):
                if card_num*k <= j:
                    dp[j] += dp[j-card_num*k]

    for gg in guesses:
        ans.append(dp[gg])
    return ans


def main(args):
    # m = 5
    # cards = [[1, 10], [5, 3], [10, 3], [25, 2], [50, 2]]
    # g = 4
    # guesses = [120, 500, 100, 168]

    while True:
        m = int(input())
        if m == 0:
            break
        cards = []
        for _ in range(m):
            a, b = map(int, input().split())
            cards.append([a, b])
        g = int(input())
        guesses = [int(input()) for _ in range(g)]
        ans = solve(m, cards, g, guesses)
        print(*ans, sep='\n')


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

Submission status: Accepted

Solution code:
# AOJ 0154 Sum of Cards
# Python3 2018.6.19 bal4u

MAX = 1001

while True:
	m = int(input())
	if m == 0: break
	ab = [0]
	for i in range(m):
		ab.append(list(map(int, input().split())))
	
	dp = [[0 for j in range(MAX)] for r in range(8)]
	dp[0][0] = 1
	for i in range(1, m+1):
		for j in range(MAX):
			if dp[i-1][j] == 0: continue;
			s = j
			for k in range(ab[i][1], -1, -1):
				if s < MAX: dp[i][s] += dp[i-1][j]
				s += ab[i][0]
	
	for i in range(int(input())):
		print(dp[m][int(input())])

Submission status: Accepted

Solution code:
while True:
  m = int(input())
  if m == 0:
    break

  nums = []
  for _ in range(m):
    a, b = map(int, input().split())
    lst = [a * i for i in range(b + 1)]
    nums.append(lst)
  
  """
  dp[x][y] ... x種類目まででyを作る場合の数
  dp[x][y] = sum(dp[x - 1][y - wk] for wk in nums[x])
  """
  
  def solve(n):
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
      dp[i][0] = 1
    for x in range(1, m + 1):
      for y in range(1, n + 1):
        dp[x][y] = sum([dp[x - 1][y - v] for v in nums[x - 1] if v <= y])
    print(dp[m][n])
    
  g = int(input())
  for _ in range(g):
    solve(int(input()))

Submission status: Accepted

Solution code:
import sys

def main():
	while True:
		m = input()
		if m == 0: return 0
		dp = {}
		dp[(0, 0)] = 1
		for i in xrange(m):
			v, c = map(int, raw_input().split())
			for j in xrange(1001):
				for k in xrange(c + 1):
					key = (i + 1, j + v * k)
					dp.setdefault(key, 0)
					dp[key] += dp.get((i, j), 0)
		n = input()
		for i in range(n):
			x = input()
			print dp.get((m, x), 0)

if __name__ == '__main__':
	sys.exit(main())

Submission status: Accepted

Solution code:
import sys
from array import array

def main():
	while True:
		m = input()
		if m == 0: return 0
		dp = [array('I', [0] * 1001) for i in range(m + 1)]
		dp[0][0] = 1
		for i in xrange(m):
			v, c = map(int, raw_input().split())
			for j in xrange(1001):
				for k in xrange(c + 1):
					next = j + v * k
					if next > 1000: continue
					dp[i + 1][next] += dp[i][j]
		n = input()
		for i in range(n):
			x = input()
			print dp[m][x]

if __name__ == '__main__':
	sys.exit(main())

Submission status: Accepted

Solution code:
while True:
    m = input()
    if m == 0:
        break
    cards = [map(int, raw_input().split()) for i in range(m)]
    dp = [[0] * 1001 for i in range(m+1)]
    dp[0][0] = 1
    for i, card in enumerate(cards, start=1):
        a, b = card
        dp[i] = dp[i-1][:]
        for num in range(a, a*b+1, a):
            for k in range(num, 1001):
                if dp[i-1][k-num] != 0:
                    dp[i][k] += dp[i-1][k-num]
    g = input()
    for i in range(g):
        n = input()
        print dp[m][n]

Submission status: Accepted

Solution code:
while 1:
    n=int(input())
    if n==0:break
    dp=[1]+[0]*3000
    for i in range(n):
        a,b=map(int,input().split())
        for j in range(1001,-1,-1):
            for k in range(1,b+1):
                dp[j+a*k]+=dp[j]
    for _ in range(int(input())):
        print(dp[int(input())])

Submission status: Accepted

Solution code:
def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break


while True:
    m = int(input())
    if m == 0:
        break

    a = [0 for i in range(7)]
    b = [0 for i in range(7)]
    for i in range(m):
        a[i],b[i] = [int(j) for j in input().split()]

    dp = [[0 for i in range(1001)] for j in range(8)]
    dp[0][0] = 1
    for i in range(7):
        for j in range(1001):
            for k in range(b[i] + 1):
                if j + a[i]*k <= 1000:
                    dp[i+1][j + a[i]*k] += dp[i][j]

    g = int(input())
    for i in range(g):
        n = int(input())
        print(dp[m][n])

Submission status: Runtime Error

Solution code:
def f(i):
    global soc, ans, ng
    for n in range(m[i][1]+1):
        soc += (m[i][0]*n)
        if ng < soc:
            soc -= m[i][0]*n
            return
        elif ng == soc:
            ans += 1
            soc -= m[i][0]*n
            return
        elif i < N-1:
            f(i+1)
        soc -= m[i][0]*n

while True:
    N = int(raw_input())
    if N == 0: break
    m = [map(int, raw_input().split()) for i in range(N)]
    g = [int(raw_input()) for i in range(input())]
    soc = 0
    ans = 0
    for ng in g:
        f(0)
        print ans
        ans = 0
        soc = 0

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)
def f(i):
    global soc, ans, ng
    for n in range(m[i][1]+1):
        soc += (m[i][0]*n)
        if ng < soc:
            soc -= m[i][0]*n
            return
        elif ng == soc:
            ans += 1
            soc -= m[i][0]*n
            return
        elif i < N-1:
            f(i+1)
        soc -= m[i][0]*n

while True:
    N = int(raw_input())
    if N == 0: break
    m = [map(int, raw_input().split()) for i in range(N)]
    g = [int(raw_input()) for i in range(input())]
    soc = 0
    ans = 0
    for ng in g:
        f(0)
        print ans
        ans = 0
        soc = 0

Submission status: Runtime Error

Solution code:
#encoding: UTF-8
price = count = n = 0
def f(tc,tp):
	global count
	if tc == n:
		if tp == price:
			count += 1
	else:
		for i in range(l[tc][1]+1):
			f(tc + 1,tp + (l[tc][0] * i))
n = int(raw_input())
l = []
while n != 0:
	for i in range(n):
		s = raw_input()
		a = s.split(" ")
		s = a[0]
		ts = a[1]
		tl = [int(s),int(ts)]
		l.append(tl)
	a = int(raw_input())
	for i in range(a):
		price = int(raw_input())
		f(0,0)
		print count
		count = 0
	n = int(raw_input())

Submission status: Runtime Error

Solution code:
R = lambda:map(int, raw_input().split())
def solve(num, s, m):
    c = 0
    if m is len(a)-1:
        #print num-s
        if (num - s % a[len(a)-1][0]
            and 0 <= num - s <= a[len(a)-1][0]*a[len(a)-1][1]): return 1
        else: return 0
    for i in xrange(a[m][1]+1):
        #print a[m], i
        c += solve(num, s+a[m][0]*i, m+1)
    return c

while 1:
    m = int(raw_input())
    if not m: break
    a = []
    for i in xrange(m):
        ss, zgok = R()
        a.append((ss, zgok))
    a.sort(reverse=True)
    n = int(raw_input())
    for i in xrange(n):
        num = int(raw_input())
        print solve(num, 0, 0)

Submission status: Runtime Error

Solution code:
def f(n):
	c=0
	while n>1:
		if n%2:n=3*n+1
		else:n/=2
		c+=1
	print c
	
while 1:
	n=input()
	if n==0:break
	f(n)