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: Wrong Answer

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(length)] for m in range(6)]
    ans = - 1
    for outer in range(6):
        if ans != -1:
            break
        for inner in range(length):
            if outer == 0:
                initial = target - pascal[inner]
                dp[outer][inner] = target - pascal[inner]
                if initial == 0:
                    ans = outer + 1
                    break
            else:
                for i in range(length):
                    nextval = dp[outer - 1][inner] - pascal[i]
                    if nextval < 0:
                        break
                    elif nextval == 0:
                        dp[outer][inner] = min(dp[outer][inner],nextval)
                        ans = outer + 1
                        break
                    dp[outer][inner] = min(dp[outer][inner],nextval)
    oddlen = len(oddpas)
    odddp = [float("inf") for n in range(oddlen)]
    oddans = -1
    for i in range(oddlen):
        val = target - oddpas[i]
        odddp[i] = val
        if val == 0:
            oddans = 1
    cnt = 1
    while True:
        #print(odddp)
        cnt += 1
        tmpdp = odddp[:]
        if oddans != -1:
            break
        for o in range(oddlen):
            for i in range(oddlen):
                nextval = odddp[o] - oddpas[i]
                if nextval < 0:
                    break
                elif nextval == 0:
                    oddans = cnt
                    break
                else:
                     tmpdp[o] = min(odddp[0],nextval)
        odddp = tmpdp
    print(str(ans) + " " + str(oddans))
    #print(odddp,oddpas,oddans,target)
    #print(dp,pascal,ans,target)

Submission status: Wrong Answer

Solution code:
def solve():
    rec = [1000000] * 1000000
    rec[0] = 0
    odd_rec = rec.copy()
    
    tetra_num = [i * (i + 1) * (i + 2) // 6 for i in range(1, 183)]
    for t1, t2 in zip(tetra_num, tetra_num[2:]):
        for i, tpl in enumerate(zip(rec[t1:t2], rec), start=t1):
            a, b = tpl
            b += 1
            if b < a:
                rec[i] = b
    
    odd_tetra_num = [t for t in tetra_num if t % 2 == 1]
    for t1, t2 in zip(odd_tetra_num, odd_tetra_num[2:]):
        for i, tpl in enumerate(zip(odd_rec[t1:t2], odd_rec), start=t1):
            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()

Submission status: Wrong Answer

Solution code:
N = 10**6

N1 = [i for i in range(N+40)]
N2 = [i for i in range(N+40)]

#N1[0] = 0
#N2[0] = 0

p = [n*(n+1)*(n+2)//6 for n in range(1,200) if n *(n+1)*(n+2)//6< N+1]
p2 = [n*(n+1)*(n+2)//6 for n in range(1,200) if n *(n+1)*(n+2)//6< N+1 and n *(n+1)*(n+2)//6 % 2 ==1 ]
#print(p2)
for p_ in p:
    if p_ > N +1:
        continue
    n = min(p_*5,N)
    for j in range(p_,n):
#        print(j)
        if N1[j] > N1[j-p_] +1:
            N1[j] = N1[j-p_]+1
for p_ in p2:
    if p_ > N +1 :
        continue
    n = min(p_*5,N)
    for j in range(p_,n):
        if N2[j] > N2[j-p_]+1:
            N2[j] = N2[j -p_]+1
print('a')
while True:
    n = int(input())
    if n == 0:
        break
    print(N1[n],N2[n])

Submission status: Wrong Answer

Solution code:
N = 10**6

N1 = [i for i in range(N+40)]
N2 = [i for i in range(N+40)]

#N1[0] = 0
#N2[0] = 0

p = [n*(n+1)*(n+2)//6 for n in range(1,200) if n *(n+1)*(n+2)//6< N+1]
p2 = [n*(n+1)*(n+2)//6 for n in range(1,200) if n *(n+1)*(n+2)//6< N+1 and n *(n+1)*(n+2)//6 % 2 ==1 ]
#print(p2)
for p_ in p:
    if p_ > N +1:
        continue
    n = min(p_*5,N)
    for j in range(p_,n):
#        print(j)
        if N1[j] > N1[j-p_] +1:
            N1[j] = N1[j-p_]+1
for p_ in p2:
    if p_ > N +1 :
        continue
    n = min(p_*5,N)
    for j in range(p_,n):
        if N2[j] > N2[j-p_]+1:
            N2[j] = N2[j -p_]+1
#print('a')
while True:
    n = int(input())
    if n == 0:
        break
    print(N1[n],N2[n])

Submission status: Wrong Answer

Solution code:
print("")

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
import collections

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


def make_reg_tetra(m):
    i, ans, flag = 1, [], reg_tetra(1)    
    while m >= flag:
        i += 1
        ans.append(flag)
        flag = reg_tetra(i)
    return ans


def make_reg_tetra_odd(m):
    return list(filter(lambda x: x % 2 != 0, make_reg_tetra(m)))


def rec_number(n, iter):
    if dp[n][len(iter)] is not None:
        return dp[n][len(iter)]
    # ???????????¶
    elif n < 0:
        return 9999
    elif n == 0:
        return 0
    # ?¶??¶??????¶
    elif len(iter) == 1:
        dp[n][len(iter)] = rec_number(n - 1, [1]) + 1
    else:
        dp[n][len(iter)] = min(rec_number(n - iter[-1], iter) + 1, rec_number(n, iter[:-1]))

    return dp[n][len(iter)]

# f = open("input.txt", "r") ## debug
arr = []
while True:
    n = int(input())
    # n = int(f.readline()) ## debug
    if n == 0:
        break
    arr.append(n)

for n in arr:
    arr_tetra, arr_tetra_odd = make_reg_tetra(n), make_reg_tetra_odd(n)
    dp = [[None]*(n+1) for j in range(n+1)]
    a = rec_number(n, arr_tetra)
    dp = [[None]*(n+1) for j in range(n+1)]
    b = rec_number(n, arr_tetra_odd)
    print(a, b)

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Here your code !

n = []
n.append(int(input()))
while min(n):
    n.append(int(input()))
triangle = [0]
pyramid = [0]
pyramid_kisu = []
m = 0
memo = []
memo_kisu = []

while pyramid[m] < max(n):
    m += 1
    triangle.append(m+triangle[m-1])
    pyramid.append(triangle[m]+pyramid[m-1])

for i in pyramid:
    if i % 2 == 1:
        pyramid_kisu.append(i)

for i in range(len(pyramid_kisu)):
    memo_kisu.append([0,[pyramid_kisu[i]]])




for i in range(m+1):
    memo.append([[0],[],[],[],[],[]])
    memo[i][1].append(pyramid[i])

for j in range(2,6):
    for i in range(1,m):
            for k in range(1,i+1):
                for l in memo[k][j-1]:
                    memo[i][j].append(pyramid[i]+l)

for question in n:
    flag = 0
    if question == 0:
        break
    else:
        for j in range(1,6):
            for i in reversed(range(1,len(memo))):
                if question in memo[i][j]:
                    ans=j
                    flag = 1
                    break
            if flag == 1:
                break
        
        flag = 0
        count = 1
        while 1:
            for i in range(len(memo_kisu)):
                if question in memo_kisu[i][count]:
                    ans_kisu = count
                    flag = 1
                else:
                    memo_kisu[i].append([])
                    for k in range(i+1):
                        for l in memo_kisu[k][count]:
                            memo_kisu[i][count+1].append(pyramid_kisu[i]+l)
            if flag == 1:
                break
            count += 1    
    print(ans,ans_kisu)

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Here your code !

n = []
n.append(int(input()))
while min(n):
    n.append(int(input()))
#triangle = [0]
pyramid = [0]
pyramid_kisu = []
m = 0
memo = []
memo_kisu = []

while pyramid[m] < max(n):
    m += 1
#    triangle.append(m+triangle[m-1])
#    pyramid.append(triangle[m]+pyramid[m-1])
    pyramid.append(int((m*(m+1)*(m+2))/6))

for i in pyramid:
    if i % 2 == 1:
        pyramid_kisu.append(i)

for i in range(len(pyramid_kisu)):
    memo_kisu.append([0,[pyramid_kisu[i]]])

for i in range(m+1):
    memo.append([[0],[],[],[],[],[]])
    memo[i][1].append(pyramid[i])

for j in range(2,6):
    for i in range(1,m):
            for k in range(1,i+1):
                for l in memo[k][j-1]:
                    memo[i][j].append(pyramid[i]+l)

kisu_len=[0]
for question in n:
    flag = 0
    if question == 0:
        break
    else:
        for j in range(1,6):
            for i in reversed(range(1,len(memo))):
                if question in memo[i][j]:
                    ans=j
                    flag = 1
                    break
            if flag == 1:
                break
        
        flag = 0
        count = 1
        while 1:
            for i in range(len(memo_kisu)):
                if question in memo_kisu[i][count]:
                    ans_kisu = count
                    kisu_len.append(ans_kisu)
                    flag = 1
                elif count >= max(kisu_len):
                    memo_kisu[i].append([])
                    for k in range(i+1):
                        for l in memo_kisu[k][count]:
                            memo_kisu[i][count+1].append(pyramid_kisu[i]+l)
            if flag == 1:
                break
            count += 1    
    print(ans,ans_kisu)
#print(kisu_len,memo_kisu[2][max(kisu_len)-1])

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Here your code !

n = []
n.append(int(input()))
while min(n):
    n.append(int(input()))
#triangle = [0]
pyramid = [0]
pyramid_kisu = []
m = 0
memo = []
memo_kisu = []

while pyramid[m] < max(n):
    m += 1
#    triangle.append(m+triangle[m-1])
#    pyramid.append(triangle[m]+pyramid[m-1])
    pyramid.append(int((m*(m+1)*(m+2))/6))

for i in pyramid:
    if i % 2 == 1:
        pyramid_kisu.append(i)

for i in range(len(pyramid_kisu)):
    memo_kisu.append([0,[pyramid_kisu[i]]])

for i in range(m+1):
    memo.append([[0],[],[],[],[],[]])
    memo[i][1].append(pyramid[i])

for j in range(2,6):
    for i in range(1,m):
            for k in range(1,i+1):
                for l in memo[k][j-1]:
                    memo[i][j].append(pyramid[i]+l)

kisu_len=[1]
for question in n:
    flag = 0
    if question == 0:
        break
    else:
        for j in range(1,6):
            for i in reversed(range(1,len(memo))):
                if question in memo[i][j]:
                    ans=j
                    flag = 1
                    break
            if flag == 1:
                break
        
        flag = 0
        count = 1
        while 1:
            for i in range(len(memo_kisu)):
                if question in memo_kisu[i][count]:
                    ans_kisu = count
                    kisu_len.append(ans_kisu)
                    flag = 1
               # if count >= max(kisu_len):
                if count >= len(memo_kisu[2])-1:
                  #  print(count,len(memo_kisu[2]))
                    memo_kisu[i].append([])
                    for k in range(i+1):
                        for l in memo_kisu[k][count]:
                            memo_kisu[i][count+1].append(pyramid_kisu[i]+l)
                 
            if flag == 1:
                break
            count += 1               
    print(ans,ans_kisu)
#print(kisu_len,memo_kisu[2][max(kisu_len)-1])
#print(kisu_len,memo_kisu)

Submission status: Accepted

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=[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]

Submission status: Accepted

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
        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())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#import time

def main():
    inputlst=[]

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

    #start=time.time()

    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番目)は(i-1番目)の自身とこれまで計算したi番目の結果しか使わないので1次元配列で済む
    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]))

    #print(time.time()-start)       



main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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
#        print("i",i,"dpm:",dpm)
    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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# AOJ 1167 - ポロック予想
# 配るDP でいってみよ～

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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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[i]: 数iを構成する最小個数
    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:


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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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()

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/1167


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]))