Problem:


Problem C: Pollock's conjecture

The nth triangular number is
defined as
the sum of the first n positive integers.
The nth tetrahedral number is
defined as
the sum of the first n triangular numbers.
It is easy to show that
the nth tetrahedral number is equal to
n(n+1)(n+2)&thinsp;&frasl;&thinsp;6.
For example,
the 5th tetrahedral number is
1+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+4+5)
= 5&times;6&times;7&thinsp;&frasl;&thinsp;6
= 35.

The first 5 triangular numbers

1, 3, 6, 10, 15

The first 5 tetrahedral numbers

1, 4, 10, 20, 35

In 1850,
Sir Frederick Pollock, 1st Baronet,
who was not a professional mathematician
but a British lawyer and Tory (currently known as Conservative) politician,
conjectured
that every positive integer can be represented
as the sum of at most five tetrahedral numbers.
Here,
a tetrahedral number may occur in the sum more than once
and,
in such a case, each occurrence is counted separately.
The conjecture has been open for more than one and a half century.

Your mission is to write a program
to verify Pollock's conjecture for individual integers.
Your program should make a calculation of
the least number of tetrahedral numbers
to represent each input integer as their sum.
In addition,
for some unknown reason,
your program should make a similar calculation
with only odd tetrahedral numbers available.

For example,
one can represent 40 as the sum of 2 tetrahedral numbers,
4&times;5&times;6&thinsp;&frasl;&thinsp;6 + 4&times;5&times;6&thinsp;&frasl;&thinsp;6,
but 40 itself is not a tetrahedral number.
One can represent 40 as the sum of 6 odd tetrahedral numbers,
5&times;6&times;7&thinsp;&frasl;&thinsp;6 + 1&times;2&times;3&thinsp;&frasl;&thinsp;6 + 1&times;2&times;3&thinsp;&frasl;&thinsp;6 + 1&times;2&times;3&thinsp;&frasl;&thinsp;6 + 1&times;2&times;3&thinsp;&frasl;&thinsp;6 + 1&times;2&times;3&thinsp;&frasl;&thinsp;6,
but cannot represent as the sum of fewer odd tetrahedral numbers.
Thus, your program should report 2 and 6 if 40 is given.

Input

The input is a sequence of lines each of which contains a single positive integer less than 106.
The end of the input is indicated by a line containing a single zero.

Output

For each input positive integer,
output a line containing two integers separated by a space.
The first integer should be
the least number of tetrahedral numbers
to represent the input integer as their sum.
The second integer should be
the least number of odd tetrahedral numbers
to represent the input integer as their sum.
No extra characters should appear in the output.

Sample Input

40
14
5
165
120
103
106
139
0

Output for the Sample Input

2 6
2 14
2 5
1 1
1 18
5 35
4 4
3 37



Sample input:
40
14
5
165
120
103
106
139
0


Sample output:
2 6
2 14
2 5
1 1
1 18
5 35
4 4
3 37

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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


def main():
    max_p = 10**6
    dp_all = [1000] * (max_p + 1)
    dp_odd = dp_all.copy()
    dp_all[0] = 0
    dp_odd[0] = 0

    pollocks = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]

    for i in range(max_p):
        for p in pollocks:
            if i + p > max_p:
                break
            if dp_all[i + p] > dp_all[i] + 1:
                dp_all[i + p] = dp_all[i] + 1
            if p % 2 and dp_odd[i + p] > dp_odd[i] + 1:
                dp_odd[i + p] = dp_odd[i] + 1

    while True:
        p = int(input())
        if p == 0:
            break
        print(dp_all[p], dp_odd[p])


main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    f = [i*(i+1)*(i+2)//6 for i in range(1,181)]
    n = 10**6-1
    dp = [i for i in range(n+1)]
    dp_odd = [i for i in range(n+1)]
    for i in range(n):
        for j in f:
            ni = i+j
            if ni <= n:
                nd = dp[i]+1
                if nd < dp[ni]:
                    dp[ni] = nd
                if j&1:
                    nd = dp_odd[i]+1
                    if nd < dp_odd[ni]:
                        dp_odd[ni] = nd
    while 1:
        n = I()
        if n == 0:
            break
        print(dp[n],dp_odd[n])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline   
    M=10**6

    dp=[0]+[M]*M
    dpo=[0]+[M]*M

    for i in range(1,200):
        t=i*(i+1)*(i+2)//6

        for j in range(t,min(5*t,M)):
            if j<t:
                dp[j]=dp[j]
            else:
                dp[j]=min(dp[j],dp[j-t]+1)
        
        if t%2==1:
            for j in range(t,M):
                if j<t:
                    dpo[j]=dpo[j]
                else:
                    dpo[j]=min(dpo[j],dpo[j-t]+1)
    
    while True:
        n=int(input())
        if n==0:
            break
        else:
            print(dp[n],dpo[n])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
"""
tetrahedral = [i*(i+1)*(i+2)//6 for i in range(1,185)]
oddtetrahedral = [i*(i+1)*(i+2)//6 for i in range(1,185,4)]
INF = float("inf")
print(oddtetrahedral)"""
dp = [1e6+1]*(int(1e6)+1)
dpodd = [1e6+1]*(int(1e6)+1)

dp[0] = dpodd[0] = 0

for i in range(1, 181):
    num = i*(i+1)*(i+2)//6
    for j, tpl in enumerate(zip(dp[num:num*3+1], dp), start=num):
        a, b = tpl
        if (b+1 < a):
            dp[j] = b+1
    if (num&1):
        for j, tpl in enumerate(zip(dpodd[num:num*34+1], dpodd), start=num):
            a, b = tpl
            if (b+1 < a):
                dpodd[j] = b+1


"""
for i in range(int(1e6)):
    num = i*(i+1)*(i+2)//6
    if (num>=1e6):
        break
    for j in range(num, int(1e6)):
        dp[j] = min(dp[j], dp[j-num]+1)
        if (num&1):
            dpodd[j] = min(dpodd[j], dpodd[j-num]+1)


dp = [INF]*int(1e6+1)
dpodd = [INF]*int(1e6+1)

for a in tetrahedral:
    if (a > int(1e6)):
        break
    dp[a] = 1
for b in oddtetrahedral:
    if (b > int(1e6)):
        break
    dpodd[b] = 1

for i in range(int(1e6)+1):
    for a in tetrahedral:
        if (i+a <= int(1e6)):
            dp[i+a] = min(dp[i+a], dp[i]+1)
    for b in oddtetrahedral:
        if (i+b <= int(1e6)):
            dpodd[i+b] = min(dpodd[i+b], dpodd[i]+1)
"""

def solve(N):
    return (dp[N], dpodd[N])

"""
    dp = [INF]*(N+1)
    dpodd = [INF]*(N+1)
    for a in tetrahedral:
        if (a > N):
            break
        dp[a] = 1
    for b in oddtetrahedral:
        if (b > N):
            break
        dpodd[b] = 1

    def reca(n):
        if (n < 0):
            return INF
        if (dp[n] != INF):
            return dp[n]
        dp[n] = min([reca(n-a)+1 for a in tetrahedral if (n-a>=0)])
        return dp[n]

    def recb(n):
        if (n < 0):
            return INF
        if (dpodd[n] != INF):
            return dpodd[n]
        dpodd[n] = min([recb(n-b)+1 for b in oddtetrahedral])
        return dpodd[n]

    ret1 = reca(N)
    ret2 = recb(N)
    return (ret1, ret2)
"""

def main():
    ans = []
    while True:
        N = int(input())
        if (N == 0):
            break
        ans.append(solve(N))

    for i in ans:
        print(*i)

main()


"""
    for i in range(N+1):
        for a in tetrahedral:
            if (i+a <= N):
                dp[i+a] = min(dp[i+a], dp[i]+1)
        for b in oddtetrahedral:
            if (i+b <= N):
                dpodd[i+b] = min(dpodd[i+b], dpodd[i]+1)
    return (dp[N], dpodd[N])
"""

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
sq = [i for i in range(200)]
for i in range(199):
    sq[i + 1] += sq[i]
for i in range(199):
    sq[i + 1] += sq[i]
ss = []
for s in sq:
    if s % 2:
        ss.append(s)

dp = defaultdict(lambda: False)
check = defaultdict(lambda: False)
for s in sq:
    dp[s] = True
    check[s] = True
dps = defaultdict(lambda: False)
checks = defaultdict(lambda: False)
for s in ss:
    dps[s] = True
    checks[s] = True

def main(n, ss, check, dp):
    q = deque()
    q.append((n, 1))
    check[n] = True
    if dp[n]:
        return 1
    while q:
        a, i = q.pop()
        for s in ss:
            aa = a - s
            if aa <= 0:
                break
            if not check[aa]:
                check[aa] = True
                q.appendleft((aa, i + 1))
            else:
                if dp[aa]:
                    return i + 1

while 1:
    n = int(input())
    if n == 0:
        break
    check = defaultdict(lambda: False)
    for s in sq:
        check[s] = True
    checks = defaultdict(lambda: False)
    for s in ss:
        checks[s] = True
    print(main(n, sq, check, dp), main(n, ss, checks,dps))

Submission status: Runtime Error

Solution code:
MAX = 10**6 - 1
inf = float("inf")
tetra_sum = [inf for i in range(MAX+1)]
tetra_sum_odd = [inf for i in range(MAX+1)]
tetra_sum[0] = 0
tetra_sum_odd[0] = 0
for n in range(1,181):
	tetra_n = n * (n+1) * (n+2) / 6
	for i in range(tetra_n,MAX+1):
		if tetra_sum[i-tetra_n] + 1 < tetra_sum[i]:
			tetra_sum[i] = tetra_sum[i-tetra_n] + 1
		if (tetra_n % 2) == 1 and tetra_sum_odd[i-tetra_n] + 1 < tetra_sum_odd[i]:
			tetra_sum_odd[i] = tetra_sum_odd[i-tetra_n] + 1
while 1:
	N = int(raw_input())
	if N == 0:
		break
	print tetra_sum[N], tetra_sum_odd[N]

Submission status: Runtime Error

Solution code:
MAX = 10**6 - 1
inf = float("inf")
tetra_n = [i*(i+1)*(i+2)/6 for i in range(1,181)]
tetra_sum = [inf for i in range(MAX+1)]
tetra_sum_odd = [inf for i in range(MAX+1)]
tetra_sum[0] = 0
tetra_sum_odd[0] = 0
tmp_max = 0
for tn in tetra_n:
	tmp_max = max(tmp_max + 4 * tn, 5 * tn)
	if (tn % 2) == 0:
		for i in range(tn,min(tmp_max,MAX)+1):	
			if tetra_sum[i-tn] + 1 < tetra_sum[i]:
				tetra_sum[i] = tetra_sum[i-tn] + 1
	else:
		for i in range(tn,MAX+1):	
			if i <= tmp_max and tetra_sum[i-tn] + 1 < tetra_sum[i]:
				tetra_sum[i] = tetra_sum[i-tn] + 1
			if tetra_sum_odd[i-tn] + 1 < tetra_sum_odd[i]:
				tetra_sum_odd[i] = tetra_sum_odd[i-tn] + 1
while 1:
	N = int(raw_input())
	if N == 0:
		break
	print tetra_sum[N], tetra_sum_odd[N]

Submission status: Runtime Error

Solution code:
MAX = 10**6 - 1
inf = float("inf")
tetra_n = [i*(i+1)*(i+2)/6 for i in range(1,181)]
tetra_sum = [inf for i in range(MAX+1)]
tetra_sum_odd = [inf for i in range(MAX+1)]
tetra_sum[0] = 0
tetra_sum_odd[0] = 0
for tn in tetra_n:
	if tn % 2 == 0:
		for i in range(tn,MAX+1):	
			if tetra_sum[i-tn] + 1 < tetra_sum[i]:
				tetra_sum[i] = tetra_sum[i-tn] + 1
	else :
		for i in range(tn,MAX+1):
			if tetra_sum[i-tn] + 1 < tetra_sum[i]:
				tetra_sum[i] = tetra_sum[i-tn] + 1
			if tetra_sum_odd[i-tn] + 1 < tetra_sum_odd[i]:
				tetra_sum_odd[i] = tetra_sum_odd[i-tn] + 1
while 1:
	N = int(raw_input())
	if N == 0:
		break
	print tetra_sum[N], tetra_sum_odd[N]

Submission status: Runtime Error

Solution code:
R = 10**6+1
T = [i*(i+1)*(2*i+1)/6 for i in xrange(145)]
dp1 = [100]*R
dp2 = [100]*R
for t in T:
    dp1[t] = 1
    for i in xrange(t,R):
        if dp1[i-t]: dp1[i] = min(dp1[i],dp1[i-t]+1)
    if t%2 == 0: continue
    dp2[t] = 1
    for i in xrange(t,R):
        if dp2[i-t]: dp1[i] = min(dp2[i],dp2[i-t]+1)
while 1:
    n = int(raw_input())
    print dp1[n],dp2[n]

Submission status: Runtime Error

Solution code:
R = 10**6+1
T = [i*(i+1)*(i+2)/6 for i in xrange(145)]
dp1 = [1e10]*R
dp2 = [1e10]*R
dp1[0] = dp2[0] = 0
for t in T:
    dp1[t] = 1
    for i in xrange(t,R):
        if dp1[i-t] < 1e10: dp1[i] = min(dp1[i],dp1[i-t]+1)
    if t%2 == 0: continue
    dp2[t] = 1
    for i in xrange(t,R):
        if dp2[i-t] < 1e10: dp2[i] = min(dp2[i],dp2[i-t]+1)

while 1:
    n = int(raw_input())
    if n == 0: break
    print dp1[n],dp2[n]

Submission status: Runtime Error

Solution code:
MAX=1000000
INF=100000
import math

def f(a):
	return (a*(a+1)*(a+2))/6



def solve(lst):
	global ans
	global n
	count=2
	while True:

		
		if ans[n]!=INF:
			return ans[n]

		keepans=[0]*(n+1)
		
		for i in range(n+1):
			if ans[i]!=INF:
				for j in range(n+1):
					if i+j<=n:
						if ans[j]!=INF and ans[i+j]>ans[i]+ans[j]:
							keepans[i+j]=ans[i]+ans[j]
							#print i,j,"=",keepans[i+j]
		
		c=0
		for l in ans:
			if keepans[c]!=0:
				ans[c]=keepans[c]
			c=c+1
		#print "----------"
		count=count+1





while True:
	n=int(raw_input())
	if n==0:
		break

	box=[]
	oddbox=[]
	ans=[INF]*(n+1)
	oddans=[INF]*(n+1)




	for i in range(200):
		num=f(i)
		if num>n: break

		box.append(num)
		if i!=0:ans[num]=1
		if num%2==1:
			oddbox.append(num)
			oddans[num]=1

	
	print solve(box)
	ans=oddans
	print solve(oddbox)

Submission status: Runtime Error

Solution code:
MAX=1000000
INF=100000
import math

def f(a):
	return (a*(a+1)*(a+2))/6



def solve(lst):
	global ans
	global n
	count=2
	while True:

		
		if ans[n]!=INF:
			return ans[n]

		keepans=list(ans)
		
		for i in range(n+1):
			if ans[i]!=INF:
				for j in range(n+1):
					if i+j<=n:
						if ans[j]!=INF and keepans[i+j]>ans[i]+ans[j] :
							keepans[i+j]=ans[i]+ans[j]
							#print i,j,"=",keepans[i+j]
		
		c=0
		for l in ans:
			if keepans[c]!=0:
				ans[c]=keepans[c]
			c=c+1
		#print "----------"
		count=count+1





while True:
	n=int(raw_input())
	if n==0:
		break

	box=[]
	oddbox=[]
	ans=[INF]*(n+1)
	oddans=[INF]*(n+1)




	for i in range(200):
		num=f(i)
		if num>n: break

		box.append(num)
		if i!=0:ans[num]=1
		if num%2==1:
			oddbox.append(num)
			oddans[num]=1

	
	print solve(box)
	ans=oddans
	print solve(oddbox)

Submission status: Runtime Error

Solution code:
MAX=1000000
INF=100000
import math

def f(a):
	return (a*(a+1)*(a+2))/6



def solve(lst):
	global ans
	global n
	
	while True:

		keepans=list(ans)

		
		for i in range(n+1):
			if ans[i]!=INF:
				for j in range(n+1):
					if ans[n]!=INF: return ans[n]
					if i+j<=n:
						if ans[j]!=INF and keepans[i+j]>ans[i]+ans[j] :
							keepans[i+j]=ans[i]+ans[j]
							print i,j,"=",keepans[i+j]
		
		ans=list(keepans)



a1=[INF]*(MAX)
a2=[INF]*(MAX)
ans=[INF]*(MAX)

while True:
	n=int(raw_input())
	if n==0:
		break

	box=[]
	oddbox=[]
	


	for i in range(200):
		num=f(i)
		if num>n: break

		box.append(num)
		if i!=0:a1[num]=1
		if num%2==1:
			oddbox.append(num)
			a2[num]=1

	ans=list(a1)
	print solve(box)
	a1=list(ans)
	ans=list(a2)
	print solve(oddbox)
	a2=list(ans)

Submission status: Runtime Error

Solution code:
MAX = 1000000
tetra = []
dp = [0] * (MAX+1)
dpodd = [0] * (MAX+1)

for i in range(1,MAX+1):
    dp[i] = i
    dpodd[i] = i


i = 0
while True:
    i += 1
    t = i * (i+1) * (i+2) / 6
    if t > MAX: break
    tetra.append(t)

for p in tetra:
    #print(p)
    for i in range(0,MAX-p):
        dp[i+p] = min(dp[i+p], dp[i]+1)
        if p % 2 == 1:
            dpodd[i+p] = min(dpodd[i+p], dpodd[i]+1)

while True:
    n = int(raw_input())
    if n == 0: break
    print dp[n],dpodd[n]

Submission status: Runtime Error

Solution code:
MAX = 1000000
tetra = []
dp = [0] * (MAX+1)
dpodd = [0] * (MAX+1)

for i in range(1,MAX+1):
    dp[i] = i
    dpodd[i] = i


i = 0
while True:
    i += 1
    t = i * (i+1) * (i+2) // 6
    if t > MAX: break
    tetra.append(t)

for p in tetra:
    #print(p)
    for i in range(0,MAX-p):
        dp[i+p] = min(dp[i+p], dp[i]+1)
        if p % 2 == 1:
            dpodd[i+p] = min(dpodd[i+p], dpodd[i]+1)

while True:
    n = int(raw_input())
    if n == 0: break
    print (dp[n],dpodd[n])

Submission status: Runtime Error

Solution code:
MAX = 1000010
tetra = []
dp = [0] * (MAX+1)
dpodd = [0] * (MAX+1)

for i in range(1,MAX+1):
    dp[i] = i
    dpodd[i] = i


i = 0
while True:
    i += 1
    t = i * (i+1) * (i+2) // 6
    if t > MAX: break
    tetra.append(t)

for p in tetra:
    #print(p)
    for i in range(0,MAX-p):
        dp[i+p] = min(dp[i+p], dp[i]+1)
        if p % 2 == 1:
            dpodd[i+p] = min(dpodd[i+p], dpodd[i]+1)

while True:
    n = int(raw_input())
    if n == 0: break
    print (dp[n],dpodd[n])

Submission status: Runtime Error

Solution code:
while 1:
    n=int(input())
    if n==0:break
    dp=[0]+[10**10]*n
    odd=[0]+[10**10]*n
    for i in range(1,n+1):
        a=i*(i+1)*(i+2)//6
        if a>n:break
        for j in range(a,n+1):
            dp[j]=min(dp[j],dp[j-a]+1)
            if a&1:odd[j]=min(odd[j],odd[j-a]+1)
    print(dp[n],odd[n])

Submission status: Runtime Error

Solution code:
with open("input.txt") as f:
    while True:
        target = int(f.readline())
        if target == 0:
            break
        pascal = []
        tmp = 1
        nexpas = 1
        oddpas = []
        while target >= nexpas:
            pascal.append(nexpas)
            if nexpas % 2 == 1:
                oddpas.append(nexpas)
            tmp += 1
            nexpas = (tmp * (tmp + 1) * (tmp + 2)) // 6
        length = len(pascal)

        dp = [float("inf") for n in range(target + 1)]
        ans = - 1
        for i in range(length):
            dp[pascal[i]] = 1
            if pascal[i] == target:
                ans = 1
        cnt = 0
        while cnt < 10:
            #print(dp)
            cnt += 1
            tmpdp = dp[:]
            if ans != -1:
                break
            else:
                for outer in range(target + 1):
                    if dp[outer] != float("inf"):
                        nowcnt = dp[outer]

                        for i in range(length):
                            nextnum = outer + pascal[i]

                            if nextnum > target:
                                break
                            elif nextnum == target:
                                ans = nowcnt + 1
                                break
                            tmpdp[nextnum] = min(dp[nextnum],nowcnt + 1)
            #print(dp,tmpdb)
            dp = tmpdp

        oddlen = len(oddpas)
        odddp = [float("inf") for n in range(target + 1)]
        oddans = -1
        for i in range(oddlen):
            odddp[oddpas[i]] = 1
            if oddpas[i] == target:
                oddans = 1
        cnt = 0
        #print(oddpas)
        while cnt < 50:
            #print(odddp)
            cnt += 1
            tmpdp = odddp[:]
            if oddans != -1:
                break
            else:
                for outer in range(target + 1):
                    if odddp[outer] != float("inf"):
                        nowcnt = odddp[outer]
                        for i in range(oddlen):
                            nextnum = outer + oddpas[i]
                            #print(nextnum)
                            if nextnum > target:
                                break
                            elif nextnum == target:
                                oddans = nowcnt + 1
                                break
                            tmpdp[nextnum] = min(odddp[nextnum],nowcnt + 1)
            odddp = tmpdp
        print(str(ans) + " " + str(oddans))
        #print(odddp,oddpas,oddans,target)
        #print(dp,pascal,ans,target)

Submission status: Runtime Error

Solution code:
while True:
    target = int(input())
    if target == 0:
        break
    pascal = []
    tmp = 1
    nexpas = 1
    oddpas = []
    while target >= nexpas:
        pascal.append(nexpas)
        if nexpas % 2 == 1:
            oddpas.append(nexpas)
        tmp += 1
        nexpas = (tmp * (tmp + 1) * (tmp + 2)) // 6
    length = len(pascal)

    dp = [float("inf") for n in range(target + 1)]
    ans = - 1
    for i in range(length):
        dp[pascal[i]] = 1
        if pascal[i] == target:
            ans = 1
    cnt = 0
    while cnt < 10:
        #print(dp)
        cnt += 1
        tmpdp = dp[:]
        if ans != -1:
            break
        else:
            for outer in range(target + 1):
                if dp[outer] != float("inf"):
                    nowcnt = dp[outer]

                    for i in range(length):
                        nextnum = outer + pascal[i]

                        if nextnum > target:
                            break
                        elif nextnum == target:
                            ans = nowcnt + 1
                            break
                        tmpdp[nextnum] = min(dp[nextnum],nowcnt + 1)
        #print(dp,tmpdb)
        dp = tmpdp

    oddlen = len(oddpas)
    odddp = [float("inf") for n in range(target + 1)]
    oddans = -1
    for i in range(oddlen):
        odddp[oddpas[i]] = 1
        if oddpas[i] == target:
            oddans = 1
    cnt = 0
    #print(oddpas)
    while cnt < 50:
        #print(odddp)
        cnt += 1
        tmpdp = odddp[:]
        if oddans != -1:
            break
        else:
            for outer in range(target + 1):
                if odddp[outer] != float("inf"):
                    nowcnt = odddp[outer]
                    for i in range(oddlen):
                        nextnum = outer + oddpas[i]
                        #print(nextnum)
                        if nextnum > target:
                            break
                        elif nextnum == target:
                            oddans = nowcnt + 1
                            break
                        tmpdp[nextnum] = min(odddp[nextnum],nowcnt + 1)
        odddp = tmpdp
    print(str(ans) + " " + str(oddans))
    #print(odddp,oddpas,oddans,target)
    #print(dp,pascal,ans,target)

Submission status: Runtime Error

Solution code:
dp = [0] + [10 ** 10] * 10**6
odd = [0] + [10 ** 10] * 10**6
for i in range(1, 10**6 + 1):
    a = i * (i + 1) * (i + 2) // 6
    if a > 10**6: break
    for j in range(a, 10**6 + 1):
        dp[j] = min(dp[j], dp[j - a] + 1)
        if a & 1: odd[j] = min(odd[j], odd[j - a] + 1)
while 1:
    n=int(input())
    if n==0:break
    print(dp[n],odd[n])

Submission status: Runtime Error

Solution code:
N=10**6
dp = [i for i in range(N+1)]
odd = [i for i in range(N+1)]
p=4;n=3
while p<=N:
    for i in range(N+1-p):
        dp[i+p]=min(dp[i+p],dp[i]+1)
        if p&1:odd[i+p]=min(odd[i+p],odd[i]+1)
    p=n*(n+1)*(n+2)//6
    n+=1

while 1:
    n=int(input())
    if n==0:break
    print(dp[n],odd[n])

Submission status: Runtime Error

Solution code:
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
   //     Scanner sc = new Scanner(System.in);
        int[] list1 = new int[180];
        int[] cnt1 = new int[1000001];
        int[] cnt2 = new int[1000001]; 
        for(int i = 0; i < 180; i++) {
            list1[i] = (i+1)*(i+2)*(i+3)/6;
        }
        // Here your code !
        for(int i = 0; i <= 1000000; i++){
            cnt1[i] = i;
            cnt2[i] = i;
        }
        
        for(int n = 3, p = 4; p <= 1000000; n++){
            for(int i = 0; i+p <= 1000000; i++){
                cnt1[i+p] = Math.min(cnt1[i+p], cnt1[i] + 1);
            }
            if(p % 2 == 1){
                for(int i = 0; i+p <= 1000000; i++){
                    cnt2[i+p] = Math.min(cnt2[i+p], cnt2[i] + 1);
                }
            }
            // p?????????????????§??´??°
            p = n * (n+1) * (n+2) / 6;
        }
        
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            int num = Integer.parseInt(br.readLine());
            if(num == 0) break;
            System.out.println(cnt1[num] + " " + cnt2[num]);
        }
    }
}

Submission status: Runtime Error

Solution code:
INF = 1000000

while True:
    n = input()
    n = int(n)

    if n == 0:
        break

    i = 1
    tetra = []
    while True:
        t = i*(1+i)*(2+i)/6
        if t <= n:
            tetra.append(int(t))
            i += 1
        else:
            break

    dp = [[INF for _ in range(n+1)] for _ in range(len(tetra)+1)]
    for i in range(len(tetra)+1):
        dp[i][0] = 0

    for i in range(len(tetra)):
        for j in range(n):
            if j + tetra[i] <= n:
                m = INF
                for k in range(i+1):
                    if dp[k+1][j] < m:
                        m = dp[k+1][j]
                dp[i+1][j+tetra[i]] = m+1

    output = INF
    for i in range(len(tetra)+1):
        if dp[i][n] < output:
            output = dp[i][n]

    print(output)

Submission status: Runtime Error

Solution code:
INF = 1000000

while True:
    n = input()
    n = int(n)

    if n == 0:
        break

    i = 1
    tetra = []
    while True:
        t = i*(1+i)*(2+i)/6
        if t <= n:
            tetra.append(int(t))
            i += 1
        else:
            break

    dp1 = [INF for _ in range(n+1)]
    dp2 = [INF for _ in range(n+1)]
    dp1[0] = 0
    dp2[0] = 0

    for i in range(n):
        for j in range(len(tetra)):
            if i + tetra[j] <= n:
                dp1[i+tetra[j]] = min(dp1[i+tetra[j]], dp1[i]+1)
                if tetra[j] % 2 == 1:
                    dp2[i+tetra[j]] = min(dp2[i+tetra[j]], dp2[i]+1)
    
    print("%d %d" % (dp1[n], dp2[n]))

Submission status: Runtime Error

Solution code:
def pollockConjection():
    inf=int(1e6)
    dp=list(range(0,inf+1))
    odp=list(range(0,inf+1))
    n=2
    s=1
    os=1
    while s<inf+1:
        s=n*(n+1)*(n+2)//6
        n+=1
        if s%2==1:
            os=s
        for i in range(0,inf+1-s):
            dp[i+s]=min(dp[i+s],dp[i]+1)
        for i in range(0,inf+1-os):
            odp[i+os]=min(odp[i+os],odp[i]+1)
    return dp,odp

if __name__=="__main__":
    dp,odp=pollockConjection()
    while True:
        N=int(input())
        if N==0:
            break
        print(dp[N],odp[N])

Submission status: Runtime Error

Solution code:
def pollockConjection():
    inf=int(1e6)
    dp=list(range(0,inf+1))
    odp=list(range(0,inf+1))
    n=2
    s=1
    os=1
    while s<inf+1:
        s=n*(n+1)*(n+2)//6
        n+=1
        if s%2==1:
            os=s
        for i in range(0,inf+1-s):
            dp[i+s]=min(dp[i+s],dp[i]+1)
            odp[i+os]=min(odp[i+os],odp[i]+1)
    return dp,odp

if __name__=="__main__":
    dp,odp=pollockConjection()
    while True:
        N=int(input())
        if N==0:
            break
        print(dp[N],odp[N])

Submission status: Runtime Error

Solution code:
def pollockConjection():
    inf=int(1e6)
    dp=list(range(0,inf+1))
    odp=list(range(0,inf+1))
    n=2
    s=1
    os=1
    while s<inf+1:
        s=n*(n+1)*(n+2)//6
        n+=1
        if s%2==1:
            os=s
        for i in range(0,inf+1-s):
            dp[i+s]=min(dp[i+s],dp[i]+1)
            odp[i+os]=min(odp[i+os],odp[i]+1)
    return dp,odp

if __name__=="__main__":
    dp,odp=pollockConjection()
　　while True:
    N=int(input())
    if N==0:
        break
    print(dp[N],odp[N])

Submission status: Runtime Error

Solution code:
import bisect
import sys
MAX = 10**6
sys.setrecursionlimit(MAX)
arr1 = [1]
arr2 = [1]
n = 1
while True:
    n += 1
    tmp = n*(n+1)*(n+2)//6
    if tmp > MAX: break
    arr1.append(tmp)
    if tmp%2:
        arr2.append(tmp)

def rec(remain, depth, mindepth, onlyodd):
    if remain == 0: return depth
    if mindepth - depth <= 1: return mindepth
    arr = arr2 if onlyodd else arr1
    i = bisect.bisect_right(arr,remain)
    if i == 1:
        return min(mindepth, depth + remain)
    for j in range(1,i):
        mindepth = rec(remain-arr[j], depth+1, mindepth, onlyodd)
    return mindepth

def solve(n, onlyodd=False):
    return rec(n,0,n,onlyodd)

while True:
    N = int(input())
    if N == 0: break
    print('{0} {1}'.format(solve(N), solve(N,True)))

Submission status: Runtime Error

Solution code:
import itertools

P1=[p*(p+1)*(p+2)/6 for p in range(1,181)]
P2=[p for p in P1 if p%2]

maxnum=1000000

A1=[999999 for x in range(maxnum+1)]
A2=[999999 for x in range(maxnum+1)]

for X in [[P1,A1],[P2,A2]]:
    P=X[0]
    A=X[1]
    tmp=P
    bk=0
    cnt=2
    for p in tmp:
        if p<maxnum:
            A[p]=1
            bk+=1
    while bk<maxnum:
        tmp2=[]
        for t in tmp:
            for p in P:
                if t+p > maxnum:    break
                if A[t+p]>cnt:
                    A[t+p]=cnt
                    bk+=1
                    tmp2.append(t+p)
        tmp=tmp2[:]
        cnt+=1
while(1):
    n=int(raw_input())
    if n==0: break
    print A1[n], A2[n]

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    m = 10**6

    a = [inf] * m
    b = [inf] * m
    a[0] = 0
    b[0] = 0
    for i in range(1,200):
        t = i * (i+1) * (i+2) // 6
        for j in range(t,m):
            if a[j] > a[j-t] + 1:
                a[j] = a[j-t] + 1
        if t % 2 == 0:
            continue
        for j in range(t,m):
            if b[j] > b[j-t] + 1:
                b[j] = b[j-t] + 1

    while True:
        n = I()
        if n == 0:
            break
        rr.append('{} {}'.format(a[n],b[n]))



    return '\n'.join(map(str, rr))


print(main())

Submission status: Runtime Error

Solution code:
def solve():
    import sys
    file_input = sys.stdin
    
    def tetra_num(n):
        for i in range(1, 181):
            t = i * (i + 1) * (i + 2) // 6
            if t <= n:
                yield t
            else:
                break
    
    while True:
        n = int(file_input.readline())
        if n == 0:
            break
        
        n_lim = 1000000
        rec = [n_lim] * (n + 1)
        rec[0] = 0
        odd_rec = [n_lim] * (n + 1)
        odd_rec[0] = 0
        
        for t in tetra_num(n):
            if t % 2 == 0:
                for i, tpl in enumerate(zip(rec[t:], rec), start=t):
                    a, b = tpl
                    rec[i] = min(a, b + 1)
            else:
                z_rec = zip(rec[t:], rec, odd_rec[t:], odd_rec)
                for i, tpl in enumerate(z_rec, start=t):
                    a, b, c, d = tpl
                    rec[i] = min(a, b + 1)
                    odd_rec[i] = min(c, d + 1)
                    
        print(rec[n], odd_rec[n])

solve()