Problem:


  ビンゴ

問題

あるプログラミングコンテストでは,競技後の懇親会でビンゴゲームをする習わしがある．しかし,このビンゴゲームで使うビンゴカードは少々特殊で,以下の条件に従って作成される．

    
 ビンゴカードは N 行 N 列のマス目に区切られており，各マス目には正整数が１つずつ書かれている．それらの整数は全て異なる．

    
 マス目に書かれている整数は 1 以上 M 以下である．

    
 ビンゴカードに書かれているN×N個の整数の合計は S である．

    
 どの列を見たときも，上から下に向かって整数は昇順に並んでいる．

    
 どのマス目の整数も，そのマス目より左の列のどの整数よりも大きい．

以下は， N = 5, M = 50, S = 685 のときのビンゴカードの例である． 

懇親会のために上の条件を満たすビンゴカードをできるだけたくさん作りたい．ただし，同一のカードを2枚以上作ってはならない．作ることができるビンゴカードの枚数の最大値を 100000 で割った余りを出力するプログラムを作成せよ．

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

入力は1行からなり, その行にはビンゴカードのサイズ N (1≤N≤7), マス目に書かれている整数の上限 M (1≤M≤2000),ビンゴカードに書かれている整数の合計 S (1≤S≤3000) を表す3つの正整数が空白区切りで書かれている．ただし, 与えられるどの入力データにおいても，条件を満たすビンゴカードを1枚以上作ることができる．

N, M, S が 0 のとき入力の終了を示す. データセットの数は 5 を超えない．

出力

データセットごとに, 作ることができるビンゴカードの枚数の最大値を 100000 で割った余りを1行に出力せよ．

入出力例

入力例

3 9 45
3 100 50
5 50 685
0 0 0

出力例

1
7
74501

3つ目の入力例に対して，作ることができるビンゴカードの枚数の最大値は 642499974501 であるので， 100000 で割った余りの 74501 を出力する． 

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
3 9 45
3 100 50
5 50 685
0 0 0


Sample output:
1
7
74501

Submission status: Wrong Answer

Solution code:
while 1:
    n, m, s = map(int, raw_input().split())
    if n == 0: break
    dp = [[0]*(s+1) for i in range(n*n+1)]
    dp[0][0] = 1
    for i in range(1, n * n + 1):
        for j in range(s+1):
            if j - i >= 0: dp[i][j] += (dp[i-1][j-i] + dp[i][j-i]) % 100000
            if j - m - 1 >= 0: dp[i][j] += (100000 - dp[i-1][j-m-1]) % 100000
    print dp[n*n][s]

Submission status: Time Limit Exceeded

Solution code:
def allocate(remains, limit_h, limit_w):
    global m
    if not remains:
        return 1
    if limit_w == 1:
        return int(remains <= limit_h)
    return sum(allocate(remains - i, i, limit_w - 1) for i in
               range(min(limit_h, remains, m - limit_w), (remains - 1) // limit_w, -1))


while True:
    n, m, s = map(int, input().split())
    if not n:
        break
    remains = s - sum(range(1, n ** 2 + 1))
    print(allocate(remains, remains, n ** 2))

Submission status: Time Limit Exceeded

Solution code:
mod=100000
while 1:
    n,m,s=map(int,raw_input().split())
    if n==m==s==0:break
    dp=[[[0]*(s+1) for _ in xrange(m+2)] for _ in xrange(2)]
    for i in xrange(n**2):
        for j in xrange(1,m+1):
            for k in xrange(1,s+1):
                if i==0:
                    if j>=k:
                        dp[(i+1)&1][j+1][k]=1
                else:
                    if j>k:
                        dp[(i+1)&1][j+1][k]=dp[(i+1)&1][j][k]
                        continue
                    dp[(i+1)&1][j+1][k]=(dp[(i+1)&1][j][k])%mod
                    dp[(i+1)&1][j+1][k]+=(dp[i&1][j][k-j])%mod
    print(dp[(n**2)&1][m+1][s]%mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
    n,m,s=map(int,input().split())
    if n==0:break
    dp=[[0 for _ in range(s+2)] for _ in range(n*n+1)]
    dp[0][0]=1
    for i,j in itertools.product(range(1,m+1),range(n*n,0,-1)):
        for k in range(i,s+1):
            dp[j][k]=(dp[j][k]+dp[j-1][k-i])%100000
    print(dp[n*n][s])

Submission status: Time Limit Exceeded

Solution code:
# AOJ 0537: Bingo
# Python3 2018.7.1 bal4u

while True:
	n, m, s = map(int, input().split())
	if n == 0: break
	n *= n
	dp = [[0 for j in range(3001)] for i in range(n+1)]
	dp[0][0] = 1
	for i in range(1, m+1):
		for j in range(n, 0, -1):
			for k in range(i, s+1):
				dp[j][k] = (dp[j][k]+dp[j-1][k-i]) % 100000;
	print(dp[n][s])

Submission status: Memory Limit Exceeded

Solution code:
mod=100000
while 1:
    n,m,s=map(int,raw_input().split())
    if n==m==s==0:break
    dp=[[[0]*(s+1) for _ in xrange(m+2)] for _ in xrange(n**2+1)]
    for j in xrange(1,m+1):
        dp[0][j][0]=1
    for i in xrange(n**2):
        for j in xrange(1,m+1):
            for k in xrange(s+1):
                if j>k:
                    dp[i+1][j+1][k]=dp[i+1][j][k]
                    continue
                dp[i+1][j+1][k]+=(dp[i+1][j][k])%mod
                dp[i+1][j+1][k]+=(dp[i][j][k-j])%mod
    print(dp[n**2][m+1][s]%mod)

Submission status: Memory Limit Exceeded

Solution code:
def listrep(n,m,s):
    tab = [[[0]*(s+1) for i in range(m+1)] for j in range(n+1)]
    for i in range(m+1):
        tab[0][i][0] = 1
    for i in range(1,n+1):
        for j in range(1,m+1):
            for k in range(1,s+1):
                tab[i][j][k] = tab[i][j-1][k]
                if j <= k:
                    tab[i][j][k] += tab[i-1][j-1][k-j]
                    if tab[i][j][k] > 100000: tab[i][j][k] -= 100000
    return tab[n][m][s]

while True:
    n,m,s = map(int,input().split())
    if n == 0 : break
    n *= n
    print(listrep(n,m,s))

Submission status: Accepted

Solution code:
DIV = 100000
while 1:
    n, m, s = map(int, raw_input().split())
    if n == 0: break
    dp = [[0]*(s+1) for i in range(n*n+1)]
    dp[0][0] = 1
    for i in range(1, n*n+1):
        for j in range(s+1):
            if j - i >= 0: dp[i][j] = (dp[i][j] + dp[i-1][j-i] + dp[i][j-i]) % DIV
            if j - m - 1 >= 0: dp[i][j] = (dp[i][j] - dp[i-1][j-m-1] + DIV) % DIV
    print dp[n*n][s]

Submission status: Accepted

Solution code:
while True:
    n, m, s = map(int, input().split())
    if not n:
        break
    n2 = n ** 2
    dpp = [0] * (s + 1)
    dpp[0] = 1

    for i in range(1, n2 + 1):
        dpn = [0] * (s + 1)
        for j in range(i * (i + 1) // 2, s + 1):
            dpn[j] += dpp[j - i] + dpn[j - i]
            if j - m - 1 >= 0:
                dpn[j] -= dpp[j - m - 1]
            dpn[j] %= 100000
        dpp = dpn

    print(dpp[s])

Submission status: Accepted

Solution code:
import itertools
while 1:
    n,m,s=map(int,input().split())
    if n==0:break
    dp=[[0 for _ in range(s+1)] for _ in range(n*n+1)]
    dp[0][0]=1
    for i,j in itertools.product(range(1,n*n+1),range(s+1)):
        if j>=i:dp[i][j]+=dp[i-1][j-i]+dp[i][j-i]
        if j-m>=1:dp[i][j]+=100000-dp[i-1][j-m-1]
        dp[i][j]%=100000
    print(dp[n*n][s])

Submission status: Accepted

Solution code:
import itertools
while 1:
    n,m,s=map(int,input().split())
    if n==0:break
    dp=[[0 for _ in range(s+1)] for _ in range(n*n+1)]
    dp[0][0]=1
    for i,j in itertools.product(range(1,n*n+1),range(s+1)):
        if j>=i:dp[i][j]+=dp[i-1][j-i]+dp[i][j-i]
        if j-m>=1:dp[i][j]-=dp[i-1][j-m-1]
        dp[i][j]%=100000
    print(dp[n*n][s])

Submission status: Accepted

Solution code:
def listrep(n,m,s):
    tab = [[0]*(s+1) for j in range(n+1)]
    tab[0][0] = 1
    for i in range(1,n+1):
        for k in range(s+1):
            if i <= k:
                tab[i][k] += tab[i][k-i] + tab[i-1][k-i]
            if k-1 >= m:
                tab[i][k] -= tab[i-1][k-1-m]
            tab[i][k] %= 100000
    return tab[n][s]

while True:
    n,m,s = map(int,input().split())
    if n == 0 : break
    n *= n
    print(listrep(n,m,s))

Submission status: Accepted

Solution code:
for e in iter(input,'0 0 0'):
 N,M,S=map(int,e.split());N*=N
 d=[[0]*-~S for _ in[0]*-~N];d[0][0]=1
 for i in range(1,N+1):
  for j in range(i,S+1):
   d[i][j]+=d[i][j-i]+d[i-1][j-i]-(M+1<=j and d[i-1][j-M-1])
 print(d[N][S]%10**5)

Submission status: Accepted

Solution code:
def main():
    while True:
        N, M, S = map(int, input().split())
        if max(N, M, S) == 0:
            break
        ans = solve(N, M, S)
        print(ans)


def solve(N, M, S):
    MOD = 10 ** 5
    p = N * N
    q = M - p
    T = S - (p * (p + 1)) // 2

    dp = [[0 for i in range(T + 1)] for j in range(p + 1)]
    dp[0][0] = 1
    for i in range(1, p + 1):
        for j in range(T + 1):
            dp[i][j] = dp[i - 1][j]
            if j - i >= 0:
                dp[i][j] += dp[i][j - i]
            if j - i - q >= 0:
                dp[i][j] -= dp[i - 1][j - i - q]

            dp[i][j] %= MOD

    ans = dp[p][T]
    # for r in dp:
    #     print(", ".join(map(str, r)))
    return ans


main()

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline
MOD = 100000


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


while 1:
    N, M, S = inpl()
    if N == 0:
        break
    N *= N
    dp = [[0] * (S + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(1, N + 1):
        for j in range(S + 1):
            if i <= j:
                dp[i][j] += dp[i][j - i] + dp[i - 1][j - i]
            if j - 1 >= M:
                dp[i][j] -= dp[i - 1][j - 1 - M]
            dp[i][j] %= MOD

    # TLE!!!
    # for i in range(1, M + 1):
    #     for j in range(1, N + 1)[::-1]:  # j - 1の値が更新されるのを防ぐために降順
    #         for k in range(i, S + 1):  # 合計値は必ずi以上になる
    #             dp[j][k] += dp[j - 1][k - i]
    #             dp[j][k] %= MOD

    print(dp[N][S])

Submission status: Runtime Error

Solution code:
def listrep(n,m,s):
    tab = [[[0]*(s+1) for j in range(n+1)]
    tab[0][0] = 1
    for i in range(1,n+1):
        for k in range(s+1):
            if i <= k:
                tab[i][k] += tab[i][k-i] + tab[i-1][k-i]
            if j-1 >= m:
                tab[i][k] -= tab[i-1][j-1-m]
    return tab[n][m][s]

while True:
    n,m,s = map(int,input().split())
    if n == 0 : break
    n *= n
    print(listrep(n,m,s))