Problem:
Problem C: Pollock's conjecture The n th triangular number is
defined as
the sum of the first n positive integers.
The n th tetrahedral number is
defined as
the sum of the first n triangular numbers.
It is easy to show that
the n th tetrahedral number is equal to n ( n +1)( n +2) ⁄ 6.
For example,
the 5th tetrahedral number is
1+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+4+5)
= 5×6×7 ⁄ 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×5×6 ⁄ 6 + 4×5×6 ⁄ 6,
but 40 itself is not a tetrahedral number.
One can represent 40 as the sum of 6 odd tetrahedral numbers,
5×6×7 ⁄ 6 + 1×2×3 ⁄ 6 + 1×2×3 ⁄ 6 + 1×2×3 ⁄ 6 + 1×2×3 ⁄ 6 + 1×2×3 ⁄ 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 10 6 .
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

Solution (Python):
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=[5 for x in range(maxnum+1)]
A2=[37 for x in range(maxnum+1)]

for X in [[P1,A1],[P2,A2]]:
    P=X[0]
    A=X[1]
    mx=A[0]
    tmp=P
    bk=0
    cnt=2
    for p in tmp:
        if p<maxnum:
            A[p]=1
            bk+=1
    while cnt<mx:
        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]

Solution (Python):
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
        mm = min(t*5,m)
        for j in range(t,mm):
            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())

Solution (Python):
def solve():
    rec = [5] * 1000000
    rec[0] = 0
    
    tetra_num = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]
    
    for i, a in enumerate(tetra_num):
        for j, b in enumerate(tetra_num[i:], start=i):
            if a + b >= 1000000:
                break
            for c in tetra_num[j:]:
                if a + b + c >= 1000000:
                    break
                rec[a + b + c] = 3
    
    for i, a in enumerate(tetra_num, start=0):
        for b in tetra_num[i:]:
            if a + b >= 1000000:
                break
            rec[a + b] = 2
    
    for n in tetra_num:
        rec[n] = 1
    
    for i, n in enumerate(rec[1:], start=1):
        if n == 3:
            for t in tetra_num:
                if i + t >= 1000000:
                    break
                if rec[i + t] == 5:
                    rec[i + t] = 4
    
    odd_rec = [1000000] * 1000000
    odd_rec[0] = 0
    
    odd_tetra_num = tetra_num[::4]
    
    for odd_t in odd_tetra_num:
        for i, tpl in enumerate(zip(odd_rec[odd_t:], odd_rec), start=odd_t):
            a, b = tpl
            b += 1
            if b < a:
                odd_rec[i] = b
    
    import sys
    file_input = sys.stdin
    n = int(file_input.readline())
    while n:
        print(rec[n], odd_rec[n])
        n = int(file_input.readline())

solve()

Solution (Python):
def solve():
    rec = [1000000] * 1000000
    rec[0] = 0
    odd_rec = rec.copy()
    
    for i in range(1, 181):
        t = i * (i + 1) * (i + 2) // 6
        for i, tpl in enumerate(zip(rec[t:t*4], rec), start=t):
            a, b = tpl
            b += 1
            if b < a:
                rec[i] = b
        if t % 2:
            for i, tpl in enumerate(zip(odd_rec[t:t*35], odd_rec), start=t):
                a, b = tpl
                b += 1
                if b < a:
                    odd_rec[i] = b
    
    import sys
    file_input = sys.stdin
    n = int(file_input.readline())
    while n:
        print(rec[n], odd_rec[n])
        n = int(file_input.readline())

solve()

Solution (Python):
def solve():
    rec = [1000000] * 1000000
    rec[0] = 0
    odd_rec = rec.copy()
    
    for i in range(1, 181):
        t = i * (i + 1) * (i + 2) // 6
        for i, tpl in enumerate(zip(rec[t:t*3+1], rec), start=t):
            a, b = tpl
            b += 1
            if b < a:
                rec[i] = b
        if t % 2:
            for i, tpl in enumerate(zip(odd_rec[t:t*34+1], odd_rec), start=t):
                a, b = tpl
                b += 1
                if b < a:
                    odd_rec[i] = b
    
    import sys
    file_input = sys.stdin
    n = int(file_input.readline())
    while n:
        print(rec[n], odd_rec[n])
        n = int(file_input.readline())

solve()

Solution (Python):
def main():
  INIT = 100
  
  query = []
  ans = []
  while True:
    q = int(input())
    if q == 0:
      break
    query.append(q)
  MAX = max(query)
  
  table = [INIT] * (MAX + 1)
  table[0] = 0
  all_item = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]
  odd_item = [i for i in all_item if i % 2]
  eve_item = [i for i in all_item if not i % 2]
  
  for v in odd_item:
    for j in range(v, MAX + 1):
      tjv = table[j - v]
      if table[j] > tjv + 1:
        table[j] = tjv + 1
  
  for q in query:
    ans.append(table[q])
  
  for v in eve_item:
    for j in range(v, MAX + 1):
      tjv = table[j - v]
      if tjv < 5 and table[j] > tjv + 1:
        table[j] = tjv + 1
  
  for i, q in enumerate(query):
    print(table[q], ans[i])

main()

Solution (Python):
def main():
  INIT = 100
  
  query = []
  ans = []
  while True:
    q = int(input())
    if q == 0:
      break
    query.append(q)
  MAX = max(query)
  
  table = [INIT] * (MAX + 1)
  table[0] = 0
  all_item = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]
  odd_item = [i for i in all_item if i % 2]
  eve_item = [i for i in all_item if not i % 2]
  
  for v in odd_item:
    for j in range(v, MAX + 1):
      tjv = table[j - v]
      if table[j] > tjv + 1:
        table[j] = tjv + 1
  
  for q in query:
    ans.append(table[q])
  
  for v in eve_item:
    for j in range(v, MAX + 1):
      tjv = table[j - v]
      if table[j] > tjv + 1:
        table[j] = tjv + 1
  
  for i, q in enumerate(query):
    print(table[q], ans[i])

main()

Solution (Python):
import sys
import copy


def solve():
    n = 10**6
    INF = 10**3
    dp = [INF] * (n + 1)
    dp[0] = 0
    dp_odd = copy.deepcopy(dp)

    for i in range(n):
        for x in arr:
            if i + x > n:
                break
            if dp[i + x] > dp[i] + 1:
                dp[i + x] = dp[i] + 1
            if x % 2:
                if dp_odd[i + x] > dp_odd[i] + 1:
                    dp_odd[i + x] = dp_odd[i] + 1

    return dp, dp_odd


arr = [1]

for i in range(1, 180):
    arr.append(arr[-1] * (i + 3) // i)

a, b = solve()


while True:
    n = int(input())
    if n == 0:
        sys.exit()
    print(a[n], b[n])

Solution (Python):


def main():
    inputlst=[]

    while 1 :
        n=int(input())
        if n==0 : break
        inputlst.append(n)

    

    lst=[]

    for i in range(1,181):
        j=i*(i+1)*(i+2)//6
        if j>=10**6 : break
        lst.append(j)

    olst=[i for i,x in enumerate(lst) if x%2==1]    

    nlst=len(lst)

    
    dp=[i for i in range(10**6)]
    dpo=[i for i in range(10**6)]


    for i in range(nlst):
        li=lst[i]
        if i in olst:
            for j in range(li,10**6):
                if dp[j-li]+1<dp[j]:
                    dp[j]=dp[j-li]+1
                if dpo[j-li]+1<dpo[j]:
                    dpo[j]=dpo[j-li]+1
        else :
            for j in range(li,10**6):
                if dp[j-li]+1<dp[j]:
                    dp[j]=dp[j-li]+1                

    for x in inputlst:
        print("{} {}".format(dp[x],dpo[x]))

    



main()

Solution (Python):
def solve():
    rec = [1000000] * 1000000
    rec[0] = 0
    odd_rec = rec.copy()

    for i in range(1, 181):
        t = i * (i + 1) * (i + 2) // 6
        for i, tpl in enumerate(zip(rec[t:t*3+1], rec), start=t):
            a, b = tpl
            b += 1
            if b < a:
                rec[i] = b
        if t % 2:
            for i, tpl in enumerate(zip(odd_rec[t:t*34+1], odd_rec), start=t):
                a, b = tpl
                b += 1
                if b < a:
                    odd_rec[i] = b

    import sys
    file_input = sys.stdin
    n = int(file_input.readline())
    while n:
        print(rec[n], odd_rec[n])
        n = int(file_input.readline())


solve()

Solution (Python):
INF = 10**20
MAX_INT = 10**6
a = [INF] * MAX_INT
b = [INF] * MAX_INT
a[0],b[0] = 0,0
for i in range(1, 200):
  t = i*(i+1)*(i+2)//6
  mm = min(t*5, MAX_INT)
  for j in range(t, mm):
    if a[j] > a[j-t]+1:
      a[j] = a[j-t]+1

  if t%2==0: continue

  for j in range(t, MAX_INT):
    if b[j] > b[j-t]+1:
      b[j] = b[j-t]+1

while True:
  N = int(input())
  if N==0: exit()
  print(a[N], b[N])

Solution (Python):
n=1000001   
i=1
p=[]
po=[]
nn=1
while nn<n:
    p.append(nn)
    if nn%2==1:
        po.append(nn)
    i+=1
    nn= i*(i+1)*(i+2)//6
np=len(p)
npo=len(po)

pp=[]
def dpf(nn,pp,nnp):
    dpm=[i for i in range(nn+1)]
    for ppi in pp[1:nnp]:
        if ppi>nn:
            break
        for j in range(ppi,nn+1):
            dpij=1+dpm[j-ppi]
            if j>=ppi and dpm[j]>dpij:
                dpm[j]=dpij

    return dpm

nlist=[]
while True:
    n=int(input())
    if n==0:
        break
    else:
        nlist.append(n)

nmax=max(nlist)
dpm1=dpf(nmax,p,np)
dpm2=dpf(nmax,po,npo)

for i in nlist:
    print(dpm1[i],dpm2[i])

Solution (Python):
import copy

item = [i *(i +1) * (i+2) //6 for i in range(1,181)]
q = []
while True:
    in_ = int(input())
    if in_ == 0:
        break
    q.append(in_)

INIT = 1000
MAX = max(q) +10
ans = [INIT] *MAX
ans[0] = 0
odd_item = [i for i in item if i % 2 ==0 ]
even_item = [i for i in item if not(i % 2 == 0)]

for i in even_item:
    for j in range(0,MAX-i):
        if ans[j+i] > ans[j] + 1:
            ans[j+i] = ans[j] + 1

ans_ = copy.deepcopy(ans)

for i in odd_item:
    for j in range(0,MAX-i):
        if ans[j+i] > ans[j] + 1:
            ans[j+i] = ans[j]+1
for i in q:
    print(ans[i],ans_[i])

Solution (Python):
from itertools import takewhile,count
from time import perf_counter as timer

M = 10**6
nums = tuple(takewhile(lambda x: x < M, (m*(m+1)*(m+2)//6 for m in count(1))))
odds = tuple(v for v in nums if v % 2)

dp0 = [(M,M)]*M
dp0[0] = (0,0)
for v,(c,i0) in enumerate(dp0):
    c += 1
    for i,n in enumerate(nums[-i0:],start=-i0):
        x = v+n
        if x >= M:
            break
        dp0[x] = min((c,-i),dp0[x])

dp1 = [(M,M)]*M
dp1[0] = (0,0)
for v,(c,i0) in enumerate(dp1):
    c += 1
    for i,n in enumerate(odds[-i0:],start=-i0):
        x = v+n
        if x >= M:
            break
        dp1[x] = min((c,-i),dp1[x])


x = int(input())
while x != 0:
    print(dp0[x][0],dp1[x][0])
    x = int(input())

Solution (Python):



import sys


def main():
    tetra_nums = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]
    N = 10 ** 6

    dp = [i for i in range(N)]
    dp_odd = [i for i in range(N)]

    for n in range(N):
        for tetra_num in tetra_nums:
            next_n = n + tetra_num

            if next_n < N:
                next_dp = dp[n] + 1
                if next_dp < dp[next_n]:
                    dp[next_n] = next_dp

                if tetra_num & 1:
                    next_dp = dp_odd[n] + 1
                    if next_dp < dp_odd[next_n]:
                        dp_odd[next_n] = next_dp

    while True:
        num = int(sys.stdin.readline())
        if num == 0:
            break
        print(dp[num], dp_odd[num])


if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    rec = [1000000] * 1000000
    rec[0] = 0
    odd_rec = rec.copy()
    
    for i in range(1, 181):
        t = i * (i + 1) * (i + 2) // 6
        for i, tpl in enumerate(zip(rec[t:t*3+1], rec), start=t):
            a, b = tpl
            b += 1
            if b < a:
                rec[i] = b
        if t % 2:
            for i, tpl in enumerate(zip(odd_rec[t:t*34+1], odd_rec), start=t):
                a, b = tpl
                b += 1
                if b < a:
                    odd_rec[i] = b
    
    import sys
    file_input = sys.stdin
    n = int(file_input.readline())
    while n:
        print(rec[n], odd_rec[n])
        n = int(file_input.readline())

solve()

Solution (Python):
def main():
    All = [i*(i+1)*(i+2)//6 for i in range(1, 182)]
    inf = 10**18
    n = 10**6
    dp = [inf]*(n+1)
    dpo = [inf]*(n+1)
    dp[0] = 0
    dpo[0] = 0
    for j in All:
        lim = min(j*5, n)
        for i in range(j, lim+1):
            dp[i] = min(dp[i-j]+1, dp[i])
        for i in range(j, n):
            if j%2==1:
                dpo[i] = min(dpo[i-j]+1, dpo[i])
    
    while 1:
        q = int(input())
        if q==0:
            break
        print(dp[q], dpo[q])

main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    tetrahedral_num = [i*(i+1)*(i+2)//6 for i in range(1, 201)]
    tetrahedral_num_odd = [i for i in tetrahedral_num if i%2==1]
    n = []
    while True:
        tmp = int(input())
        if tmp==0:
            break
        else:
            n.append(tmp)
    max_n = max(n)

    
    dp = [float('inf')]*(max_n+1)
    dp[0] = 0
    for i in range(1, max_n+1):
        tmp = []
        for j in tetrahedral_num:
            if i-j>=0:
                tmp.append(dp[i-j])
        dp[i] = min(tmp) + 1

    dp_odd = [float('inf')]*(max_n+1)
    dp_odd[0] = 0
    for i in range(1, max_n+1):
        tmp = []
        for j in tetrahedral_num_odd:
            if i-j>=0:
                tmp.append(dp_odd[i-j])
        dp_odd[i] = min(tmp) + 1

    for i in n:
        print(dp[i], dp_odd[i])

if __name__ == '__main__':
    resolve()

Solution (Python):
def main():
  INIT = 100
  
  query = []
  ans = []
  while True:
    q = int(input())
    if q == 0:
      break
    query.append(q)
  MAX = max(query)
  
  table = [INIT] * (MAX + 1)
  table[0] = 0
  all_item = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]
  odd_item = [i for i in all_item if i % 2]
  eve_item = [i for i in all_item if not i % 2]
  
  for v in odd_item:
    for j in range(v, MAX + 1):
      tjv = table[j - v]
      if table[j] > tjv + 1:
        table[j] = tjv + 1
  
  for q in query:
    ans.append(table[q])
  
  for v in eve_item:
    for j in range(v, MAX + 1):
      tjv = table[j - v]
      if table[j] > tjv + 1:
        table[j] = tjv + 1
  
  for i, q in enumerate(query):
    print(table[q], ans[i])

main()

Solution (Python):
def main():
  INIT = 100
  
  query = []
  ans = []
  while True:
    q = int(input())
    if q == 0:
      break
    query.append(q)
  MAX = max(query)
  
  table = [INIT] * (MAX + 1)
  table[0] = 0
  all_item = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]
  odd_item = [i for i in all_item if i % 2]
  eve_item = [i for i in all_item if not i % 2]
  
  for v in odd_item:
    for j in range(v, MAX + 1):
      tjv = table[j - v]
      if table[j] > tjv + 1:
        table[j] = tjv + 1
  
  for q in query:
    ans.append(table[q])
  
  for v in eve_item:
    for j in range(v, MAX + 1):
      tjv = table[j - v]
      if table[j] > tjv + 1:
        table[j] = tjv + 1
  
  for i, q in enumerate(query):
    print(table[q], ans[i])

main()

Solution (Python):
def main():
  INIT = 100
  
  query = []
  ans = []
  while True:
    q = int(input())
    if q == 0:
      break
    query.append(q)
  MAX = max(query)
  
  table = [INIT] * (MAX + 1)
  table[0] = 0
  all_item = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]
  odd_item = [i for i in all_item if i % 2]
  eve_item = [i for i in all_item if not i % 2]
  
  for v in odd_item:
    for j in range(v, MAX + 1):
      tjv = table[j - v]
      if table[j] > tjv + 1:
        table[j] = tjv + 1
  
  for q in query:
    ans.append(table[q])
  
  for v in eve_item:
    for j in range(v, MAX + 1):
      tjv = table[j - v]
      if table[j] > tjv + 1:
        table[j] = tjv + 1
  
  for i, q in enumerate(query):
    print(table[q], ans[i])

main()

Solution (Python):


def calc():
    n = 10**6

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

    dp = [1000] * (n+1)
    dp_odd = dp.copy()
    dp[0] = 0
    dp_odd[0] = 0
    for j in range(n):
        for d in dataset:
            if j + d > n:
                break
            if dp[j + d] > dp[j] + 1:
                dp[j + d] = dp[j] + 1
            if d%2:
                if dp_odd[j + d] > dp_odd[j] + 1:
                    dp_odd[j + d] = dp_odd[j] + 1

    return dp, dp_odd


all, odd = calc()

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

    a = all[n]
    o = odd[n]

    print(a, o)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    Q=[]
    while True:
        N=int(input())
        if N==0:
            break
        Q.append(N)
    MAX_Q=max(Q)
    A=tuple((i+1)*(i+2)*(i+3)//6 for i in range(182))
    A_odd=tuple(i for i in A if i%2)
    A_even=tuple(i for i in A if i%2==0)
    dp=[INF]*(MAX_Q+1)
    dp[0]=0
    for x in A_odd:
        for k in range(x,MAX_Q+1):
            if dp[k]>dp[k-x]+1:
                dp[k]=dp[k-x]+1
    ans=[]
    for q in Q:
        ans.append(dp[q])
        
    for x in A_even:
        for k in range(x,MAX_Q+1):
            dp[k]=min(dp[k],dp[k-x]+1)
    for i,q in enumerate(Q):
        print(dp[q],ans[i])


if __name__ == '__main__':
    main()

Solution (Python):



def porok(n):
    return n * (n+1) * (n+2) // 6


def dp_1(n):
    for j in poroks_odd:
        for i in range(j, n+1):
            tmp = dp[i-j] + 1
            if dp[i-j] + 1 < dp[i]:
                dp[i] = dp[i-j] + 1


def dp_2(n):
    for j in poroks_even:
        for i in range(j, n+1):
            tmp = dp[i-j] + 1
            if dp[i-j] + 1 < dp[i]:
                dp[i] = dp[i-j] + 1


if __name__ == "__main__":
    query_list = []
    ans_even = []
    while(True):
        n = int(input())
        if n == 0:
            break
        query_list.append(n)

    poroks = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]
    poroks_odd = [
        porok_number for porok_number in poroks if porok_number % 2 == 1]
    poroks_even = [
        porok_number for porok_number in poroks if porok_number % 2 == 0]
    dp = [100] * (max(query_list)+1)
    dp[0] = 0

    dp_1(max(query_list))

    for q in query_list:
        ans_even.append(dp[q])

    dp_2(max(query_list))

    for i, q in enumerate(query_list):
        print('{} {}'.format(dp[q], ans_even[i]))

Solution (Python):
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()

Solution (Python):

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


if __name__ == "__main__":
    solve()

Solution (Python):
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()

Solution (Python):
"""
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])
"""

Solution (Python):
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))

Solution (Python):
import copy

item = [i *(i +1) * (i+2) //6 for i in range(1,181)]
q = []
while True:
    in_ = int(input())
    if in_ == 0:
        break
    q.append(in_)

INIT = 1000
MAX = max(q) +10
ans = [INIT] *MAX
ans[0] = 0
odd_item = [i for i in item if i % 2 ==0 ]
even_item = [i for i in item if not(i % 2 == 0)]

for i in even_item:
    for j in range(0,MAX-i):
        if ans[j+i] > ans[j] + 1:
            ans[j+i] = ans[j] + 1

ans_ = copy.deepcopy(ans)

for i in odd_item:
    for j in range(0,MAX-i):
        if ans[j+i] > ans[j] + 1:
            ans[j+i] = ans[j]+1
for i in q:
    print(ans[i],ans_[i])