Problem:


整数の和 II

0 から 100 の数字から異なる n 個の数を取り出して合計が s となる組み合わせの数を出力するプログラムを作成してください。n 個の数はおのおの 0 から 100 までとし、１つの組み合わせに同じ数字は使えません。たとえば、n が 3 で s が6 のとき、3 個の数字の合計が 6 になる組み合わせは、

1 + 2 + 3 = 6
0 + 1 + 5 = 6
0 + 2 + 4 = 6

の 3 通りとなります。

Input

複数のデータセットが与えられます。各データセットに n ( 1 ≤ n ≤ 9 ) と s ( 0 ≤ s ≤ 1000 ) が１つのスペースで区切られて１行に与えられます。n と s が共に 0 のとき入力の最後とします。

データセットの数は 50 を超えません。

Output

各データセットに対して、n 個の整数の和が s になる組み合わせの数を１行に出力して下さい。

組み合わせの数が 1010を超える入力は与えられません。

Sample Input

3 6
3 1
0 0

Output for the Sample Input

3
0



Sample input:
3 6
3 1
0 0


Sample output:
3
0

Submission status: Wrong Answer

Solution code:
m=1001
A=range(9)
d=[[0]*m for i in A]
for i in range(101):
  for j in A[:-1][::-1]:
    for k in range(m-i): d[j][k+i]+=d[j-1][k]
  d[0][i]=1
while 1:
  n,s=map(int,raw_input().split())
  if n==s==0: break
  print d[n-1][s]

Submission status: Wrong Answer

Solution code:
import itertools

while 1:
	n,s=list(map(int,input().split()))
	if not n and not s:break 
	print(len(list(filter(lambda x:x==s,map(sum,itertools.combinations(range(10),n))))))

Submission status: Wrong Answer

Solution code:
dp = [[0] * 1100 for u in xrange(10)]
dp[0][0] = 1
for i in xrange(100):
    for ii in xrange(i,1000):
        for iii in xrange(9,0,-1):
            dp[iii][ii] += dp[iii-1][ii-i]
while True:
    n,s = map(int,raw_input().split())
    if (n,s) == (0,0):
        break
    print dp[n][s]

Submission status: Wrong Answer

Solution code:
dp = [[0] * 1100 for u in xrange(10)]
dp[0][0] = 1
for i in xrange(101):
    for ii in xrange(i,1000):
        for iii in xrange(9,0,-1):
            dp[iii][ii] += dp[iii-1][ii-i]
while True:
    n,s = map(int,raw_input().split())
    if (n,s) == (0,0):
        break
    print dp[n][s]

Submission status: Time Limit Exceeded

Solution code:
def dp(m,n,s):
    if n == 1:
        if s > 100 or s < m:
            return 0
        else:
            return 1
    else:
        sum_ = 0
        for i in range(m,min(s,100)+1):
            sum_ += dp(i+1,n-1,s-i)
        return sum_

while(1):
    n,s = [int(i) for i in input().split()]
    if n == 0 and s == 0:
        break
    print(dp(0,n,s))

Submission status: Time Limit Exceeded

Solution code:
def dp(m,n,s):
    if n == 1:
        if s > 100 or s < m:
            return 0
        else:
            return 1
    else:
        sum_ = 0
        for i in range(m,min(s,100)+1):
            sum_ += dp(i,n-1,s-i)
        return sum_

fact = [0,0,1,3,6,10,15,21,28,36,45]

while(1):
    n,s = [int(i) for i in input().split()]
    if n == 0 and s == 0:
        break
    print(dp(0,n,s-fact[n]))

Submission status: Time Limit Exceeded

Solution code:
def dp(m,n,s):
    if n == 1:
        if s > 100 or s < m:
            return 0
        else:
            return 1
    elif n*m > s:
        return 0
    else:
        sum_ = 0
        for i in range(m,min(s,100)+1):
            sum_ += dp(i,n-1,s-i)
        return sum_

fact = [0,0,1,3,6,10,15,21,28,36,45]

while(1):
    n,s = [int(i) for i in input().split()]
    if n == 0 and s == 0:
        break
    print(dp(0,n,s-fact[n]))

Submission status: Time Limit Exceeded

Solution code:
m=1001
while 1:
  n,s=map(int,raw_input().split())
  if n==s==0: break
  A=range(n)
  d=[[0]*m for i in A]
  for i in range(101):
    for j in A[::-1]:
      if j==0: d[j][i]=1
      else:
        for k in range(m):
          if k+i<m: d[j][k+i]+=d[j-1][k]
  print d[n-1][s]

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        n,s = map(int,raw_input().split())
    except EOFError:
        break
    if (n,s) == (0,0):
        break
    
    if s == 0 or s == 1 or s == 2:
        print 0
    else:    
        ls = []
        for k in range(s):
            for l in range(1,s):
                if k + l > s:
                    break
                for m in range(2,s):
                    tmp = k + l + m
                    if tmp == s and k!=l and l!=m and m!=k:
                        tmp2 = tuple(sorted((k,l,m)))
                        ls.append(tmp2)
                        break
        print len(set(ls))

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        n,s = map(int,raw_input().split())
    except EOFError:
        break
    if (n,s) == (0,0):
        break
    
    if s == 0 or s == 1 or s == 2:
        print 0
    else:    
        ls = []
        for k in range(s):
            for l in range(1,s):
                if k + l > s:
                    break
                for m in range(s,1,-1):
                    tmp = k + l + m
                    if tmp == s and k!=l and l!=m and m!=k:
                        tmp2 = tuple(sorted((k,l,m)))
                        ls.append(tmp2)
                        break
        print len(set(ls))

Submission status: Time Limit Exceeded

Solution code:
def dfs(p, c, s):
    if c==n:
        return not s
    if p==-1:
        return 0
    if memo[s][p][c] != -1:
        return memo[s][p][c]
    ret = 0
    for i in xrange(min(p, s), -1, -1):
        ret += dfs(i-1, c+1, s-i)
    memo[s][p][c] = ret
    return ret

while 1:
    n, s = map(int, raw_input().split())
    if n==0:
        break
    memo = [[[-1]*(n+1) for i in xrange(101)] for j in xrange(s+1)]
    print dfs(min(s, 100), 0, s)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from sys       import stdin
sample = [int(_) for _ in range(101)]

for _ in stdin.readlines() :
    n, s = map(int, _.split())
    if n == 0 and s == 0 : break
    print(len([_2 for _2 in combinations(sample, n) if sum(_2) == s]))

Submission status: Time Limit Exceeded

Solution code:
from copy      import copy
from itertools import combinations
from sys       import stdin
sample = [_ for _ in range(101)]

for _ in stdin.readlines() :
    n, s = map(int, _.split())
    if n == 0 and s == 0 : break
    print(len([_2 for _2 in combinations(sample[:s], n) if sum(_2) == s]))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from sys       import stdin
sample = [_ for _ in range(101)]
 
for _ in stdin.readlines() :
    n, s = map(int, _.split())
    if n == 0 and s == 0 : break
    
    print(len([_2 for _2, _3 in enumerate(combinations(sample[:s], n)) if sum(_3) == s]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

while True:
    n, s = map(int, input().split())
    count = 0
    if n == 0:
        break
    for c in itertools.combinations([i for i in range(100)], n):
        if sum(c) == s:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
while True:
    n,s=map(int,raw_input().split())
    if n==s==0:break
    cnt=0
    for i in itertools.combinations(range(101),n):
        if len(set(i))==n and sum(i)==s:
            cnt+=1
    print cnt

Submission status: Time Limit Exceeded

Solution code:
import itertools
while True:
    n,s=map(int,raw_input().split())
    if n==s==0:break
    cnt=0
    for i in itertools.combinations(range(101),n):
        if len(set(i))==n and sum(i)==s:
            cnt+=1
        if i[0]>=s:break
    print cnt

Submission status: Time Limit Exceeded

Solution code:
import itertools
while True:
    n,s=map(int,raw_input().split())
    if n==s==0:break
    cnt=0
    for i in itertools.combinations(range(101),n):
        if sum(i)==s:
            cnt+=1
        if i[0]>=s:break
    print cnt

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit
from itertools import combinations


def count(n, s):
    count = 0
    for a in combinations(range(101), n):
        if sum(a) == s:
            count += 1
    return count


def main(readline=stdin.readline):
    for line in stdin:
        n, s = (int(s) for s in line.split())
        if not n and not s:
            exit()
        print(count(n, s))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def mx(ls,n):
    sm = 0
    for i in range(n):
        sm += ls.pop()
    return sm

def mn(ls,n):
    sm = 0
    for i in range(n):
        sm += ls.pop(0)
    return sm

def soi(ls,n,s):
    if n == 0:
        if s == 0:
            return 1
        else:
            return 0
    else:
        count = 0
        l = len(ls)
        for i in range(l):
            rls = ls[:]
            k = rls.pop(i)
            if s-k >= mn(rls,n-1):
                if s-k <= mx(rls,n-1):
                    count += soi(rls,n-1,s-k)
                else:
                    break
        return count

ls = [i for i in range(101)]
while True:
    n, s = map(int, raw_input().split())
    if n == 0:
        break
    print soi(ls,n,s)

Submission status: Time Limit Exceeded

Solution code:
def soi(n,s,m):
    if n == 0:
        if s == 0:
            return 1
        else:
            return 0
    else:
        count = 0
        for i in range(m,101):
            if s-i >= 0:
                count += soi(n-1,s-i,i+1)
        return count

while True:
    n, s = map(int, raw_input().split())
    if n == 0:
        break
    print soi(n,s,0)

Submission status: Time Limit Exceeded

Solution code:
ls = [i for i in range(101)]
def comb(n,s,sp):
	if n == 0:
		return 1 if s == 0 else 0
	if sp+n > 100: return 0
	mn,mx = sum(ls[sp:sp+n]),sum(ls[::-1][:n])
	if s < mn or mx < s: return 0
	elif mn == s or mx == s: return 1
	
	sm = 0
	for i in range(sp,101):
		if ls[i] > s:
			break
		sm += comb(n-1,s-ls[i],i+1)
	return sm

while True:
	n,s = map(int, raw_input().split())
	if n == 0: break
	print comb(n,s,0)

Submission status: Memory Limit Exceeded

Solution code:
import itertools
while 1:
    k,s=map(int,input().split())
    if k==0:break
    print(sum([1 if sum(i)==s else 0 for i in itertools.combinations(range(101),k)]))

Submission status: Memory Limit Exceeded

Solution code:
from itertools import combinations as C
while True:
    n,s=map(int, input().split())
    if n==0:break
    print(sum([1 for l in list(C(range(s), n)) if sum(l)==s]))

Submission status: Memory Limit Exceeded

Solution code:
import itertools
import sys
def main():
    for line in sys.stdin:
        n, s = map(int, line.split())
        if n == 0 and s == 0:
            break
        else:
            seq = [i for i in range(0, 101)]
            A = list(itertools.combinations(seq, n))
            c = 0
            for i in range(len(A)):
                if sum(A[i]) == s:
                    c += 1
            print(c)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
m=1001
A=range(9)
d=[[0]*m for i in A]
for i in range(101):
  for j in A[::-1]:
    if j==0: d[j][i]=1
    else:
      for k in range(m):
        if k+i<m: d[j][k+i]+=d[j-1][k]
while 1:
  n,s=map(int,raw_input().split())
  if n==s==0: break
  print d[n-1][s]

Submission status: Accepted

Solution code:
m=1001
A=range(9)
d=[[0]*m for i in A]
for i in range(101):
  for j in A[::-1]:
    if j==0: d[j][i]=1
    else:
      for k in range(m-i): d[j][k+i]+=d[j-1][k]
while 1:
  n,s=map(int,raw_input().split())
  if n==s==0: break
  print d[n-1][s]

Submission status: Accepted

Solution code:
m=1001
d=[[0]*m for i in range(10)]
d[0][0]=1
for i in range(101):
  for j in range(9,0,-1):
    for k in range(m-i): d[j][k+i]+=d[j-1][k]
while 1:
  n,s=map(int,raw_input().split())
  if n==s==0: break
  print d[n][s]

Submission status: Accepted

Solution code:
m=1001
A=range(10)
d=[[0]*m for i in A]
d[0][0]=1
for i in range(101):
  for j in A[1:][::-1]:
    for k in range(m-i): d[j][k+i]+=d[j-1][k]
while 1:
  n,s=map(int,raw_input().split())
  if n==s==0: break
  print d[n][s]

Submission status: Accepted

Solution code:
m=1001
A=range(9)
d=[[0]*m for i in A]
for i in range(101):
  for j in A[1:][::-1]:
    for k in range(m-i): d[j][k+i]+=d[j-1][k]
  d[0][i]=1
while 1:
  n,s=map(int,raw_input().split())
  if n==s==0: break
  print d[n-1][s]

Submission status: Accepted

Solution code:
while 1:
    n, s = map(int, raw_input().split())
    if n==0:
        exit(0)
    dp = [[0]*(s+1) for _ in xrange(n+1)]
    dp[0][0] = 1
    for i in xrange(min(s+1, 101)):
        si1 = s-i+1
        for k in xrange(n, 0, -1):
            dp_k = dp[k]; dp_k1 = dp[k-1]
            for j in xrange(si1):
                dp_k[i+j] += dp_k1[j]
    print dp[n][s]

Submission status: Accepted

Solution code:
dp = [[0]*(1001) for _ in xrange(10)]
dp[0][0] = 1
for i in xrange(101):
    si1 = 1001-i
    for k in xrange(9, 0, -1):
        dp_k = dp[k]; dp_k1 = dp[k-1]
        for j in xrange(si1):
            dp_k[i+j] += dp_k1[j]
while 1:
    n, s = map(int, raw_input().split())
    if n==0:
        exit(0)
    print dp[n][s]

Submission status: Accepted

Solution code:
l=[[0]*1001 for i in range(10)]
l[0][0]=1
for i in range(101):
    for j in range(9,0,-1):
        for k in range(i,1000):
            l[j][k]+=l[j-1][k-i]
while 1:
    n,k=map(int,raw_input().split())
    if n==k==0:
        break
    print l[n][k]

Submission status: Accepted

Solution code:
A=[[[0 for k in range(1001)] for j in range(101)] for i in range(10)]
for j in range(101):
    A[1][j][j]=1
for i in range(2,10):
    for j in range(101):
        for k in range(j,i*j):
            for m in range((k-j)/(i-1),j):
                A[i][j][k]+=A[i-1][m][k-j]
while(1):
    [n,s]=[int(x) for x in raw_input().split()]
    if n==0:    break
    ans=0
    for j in range(101):
        ans+=A[n][j][s]
    print ans

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
now...今注目する値
used...使った数字の数
sum...それまでの合計

dp[now][used][sum]...nowまででused個の数字を使って合計sumの場合の数
dp[now][used][sum] = dp[now - 1][used - 1][sum - now] + dp[now - 1][used][sum] (used >= 1 and sum >= now)
                     dp[now - 1][used][sum]                                    (used == 0  or  sum < now)
"""
dp = [[[0 for _ in range(1001)] for _ in range(10)] for _ in range(101)]
dp[0][1][0] = 1
dp[0][0][0] = 1

for now in range(1, 101):
  for used in range(10):
    for s in range(1001):
      if used >= 1 and s >= now:
        dp[now][used][s] = dp[now - 1][used - 1][s - now] + dp[now - 1][used][s]
      else:
        dp[now][used][s] = dp[now - 1][used][s]

while True:
  n, s = map(int, input().split())
  if not n:
    break
  print(dp[100][n][s])

Submission status: Accepted

Solution code:
"""
now...今注目する値
used...使った数字の数
sum...それまでの合計

dp[now][used][sum]...nowまででused個の数字を使って合計sumの場合の数

dp[now][used][sum] = dp[now - 1][used - 1][sum - now] + dp[now - 1][used][sum] (used >= 1 and sum >= now)
                     dp[now - 1][used][sum]                                    (used == 0  or  sum < now)


2次元化

dp[used][sum]...used個の数字を使って合計sumの場合の数

dp[used][sum] = dp[used - 1][sum - now] + dp[used][sum] (used >= 1 and sum >= now)

ただし、usedの大きい順に更新する(更新がかぶるため)
"""

dp = [[0 for _ in range(1001)] for _ in range(10)]
dp[1][0] = 1
dp[0][0] = 1

for now in range(1, 101):
  for used in range(9, 0, -1):
    for s in range(now, 1001):
      dp[used][s] = dp[used - 1][s - now] + dp[used][s]

while True:
  n, s = map(int, input().split())
  if not n:
    break
  print(dp[n][s])

Submission status: Accepted

Solution code:
dp = [[0 for _ in range(1001)] for _ in range(10)]
dp[1][0] = dp[0][0] = 1

for now in range(1, 101):
  for used in range(9, 0, -1):
    dpu = dp[used]
    dpu_1 = dp[used - 1]
    for s in range(now, 1001):
      dpu[s] = dpu_1[s - now] + dpu[s]

while True:
  n, s = map(int, input().split())
  if not n:
    break
  print(dp[n][s])

Submission status: Accepted

Solution code:
# AOJ 0097 Sum of Integers II
# Python3 2018.6.15 bal4u

dp = [[0 for s in range(1001)] for n in range(11)]
dp[0][0] = 1
for k in range(101):
	for n in range(9, -1, -1):
		for s in range(1001-k):
			dp[n+1][s+k] += dp[n][s]

while True:
	n, s = list(map(int, input().split()))
	if n == 0: break
	print(dp[n][s])

Submission status: Accepted

Solution code:
dp = [[0] * 1100 for u in xrange(10)]
dp[0][0] = 1
for i in xrange(101):
    for ii in xrange(9,0,-1):
        for iii in xrange(i,1000):
            dp[ii][iii] += dp[ii-1][iii-i]
while True:
    n,s = map(int,raw_input().split())
    if (n,s) == (0,0):
        break
    print dp[n][s]

Submission status: Accepted

Solution code:
dp=[[0]*1001 for i in range(11)]
dp[0][0]=1
for i in range(101):
    for j in range(10)[::-1]:
        for k in range(1001-i):
            dp[j+1][k+i]+=dp[j][k]
while True:
    n,s=map(int,raw_input().split())
    if n==s==0:break
    print dp[n][s]

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def make_number_of_combination():
    pre = [[0] * 10 for _ in xrange(1001)]
    now = [[0] * 10 for _ in xrange(1001)]

    for a in xrange(101):
        now[a][0] = 1
        for i in xrange(1001):
            if i+a > 1000:
                break
            for j in xrange(9):
                now[i+a][j+1] += pre[i][j]

        for i in xrange(1001):
            for j in xrange(10):
                pre[i][j] = now[i][j]

    return pre


def main():
    ans = make_number_of_combination()
    for line in stdin:
        n, s = (int(s) for s in line.split())
        if not n and not s:
            exit()
        print(ans[s][n-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
dp = [[0] * 1001 for i in range(11)]
dp[0][0] = 1
for i in range(101):
    for j in range(9, -1, -1):
        for k in range(0, 1001 - i):
            dp[j + 1][k + i] += dp[j][k]
 
while True:
    n, s = map(int, raw_input().split())
    if (n,s) == (0,0):
        break
    print dp[n][s]

Submission status: Accepted

Solution code:
dp = [ [0]*1001 for x in range(11)]
dp[0][0] = 1
for i in range(101):
    for j in range(9,-1,-1):
        for k in range(1001-i):
            dp[j+1][k+i] += dp[j][k]

while 1:
    n, s = map(int, raw_input().split())
    if (n, s) == (0, 0): break
    print dp[n][s]

Submission status: Accepted

Solution code:
ls = [[0]*1001 for i in range(10)]
ls[0][0] = 1
for i in range(101):
	for j in range(9,0,-1):
		for k in range(i,1000):
			ls[j][k] += ls[j-1][k-i] 
	

while True:
	n,s = map(int, raw_input().split())
	if n == 0: break
	print ls[n][s]

Submission status: Accepted

Solution code:
dp = [[0 for j in range(1001)] for i in range(10)]
dp[0][0] = 1
for j in range(1, 1001):
  dp[0][j] = 0
for k in range(0, 101):
  for i in range(9, 0, -1):
    for j in range(k, 1001):
      dp[i][j] += dp[i - 1][j - k]

while True:
  n, s = map(int, input().split())
  if n + s == 0:
    break
  print(dp[n][s])

Submission status: Accepted

Solution code:
ans = [[0 for i in range(1001)] for j in range(11)]
ans[0][0] = 1

for i in range(101):
     for n in range(9, -1, -1):
         for s in range(1001 - i):
             ans[n + 1][s + i] += ans[n][s]

while True:
    n, s = map(int, input().split())
    if n == 0:
        break
    print(ans[n][s])

Submission status: Runtime Error

Solution code:
while True:
    try:
        n,s = map(int,raw_input().split())
    except EOFError:
        break
    if (n,s) == (0,0):
        break
    
    if s == 0 or s == 1 or s == 2:
    else:    
        ls = set([])
        for k in range(s):
            for l in range(1,s):
                if k + l > s:
                    break
                for m in range(2,s):
                    tmp = k + l + m
                    if tmp == s and k!=l and l!=m and m!=k:
                        tmp2 = tuple(sorted((k,l,m)))
                        ls.add(tmp2)
                        break
        print len(ls)

Submission status: Runtime Error

Solution code:
import itertools

while True:
	n,s = map(int,raw_input().split())
	if n == 0 and s == 0:
		break
	
	num = list(itertools.combinations(xrange(101), n))
	
	count = 0
	for var in num:
		if sum(var) == s:
			count += 1
			
	print count

Submission status: Runtime Error

Solution code:
dp = [[0] * 1001 for i in range(11)]
dp[0][0] = 1
for i in range(101):
    for j in range(9, -1, -1):
        for k in range(0, 1001 - i):
            dp[j + 1][k + i] += dp[j][k]

while True:
    n, s = map(int, raw_input().split())
    print dp[n][s]

Submission status: Runtime Error

Solution code:
memo = [[[-1 for i in xrange(101)] for j in xrange(10)] for k in xrange(1001)]
def dfs(rest, now, cnt):
    if rest==0 and now==0:
        return 1
    if now==0 or cnt==-1:
        return 0
    if memo[rest][now][cnt]!=-1:
        return memo[rest][now][cnt]
    memo[rest][now][cnt] = 0
    for i in xrange(min(cnt, rest), -1, -1):
        memo[rest][now][cnt] += dfs(rest-i, now-1, i-1)
    return memo[rest][now][cnt]
while True:
    n, s = map(int, raw_input().split())
    print dfs(s, n, 100)