Pollock's conjecture

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

Problem C: ポロック予想

n 番目の正三角形数は,最初の n 個の正整数の和と定義される. n 番目の正四面体数は,最初の n 個の正三角形数の和と定義される. 簡単に示せるように,n 番目の正四面体数は n(n+1)(n+2) ⁄ 6 に等しい. たとえば,5番目の正四面体数は 1+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+4+5) = 5×6×7 ⁄ 6 = 35 である.

最初の5個の正三角形数 1, 3, 6, 10, 15
Tr[1] Tr[2] Tr[3] Tr[4] Tr[5]
最初の5個の正四面体数 1, 4, 10, 20, 35
Tet[1] Tet[2] Tet[3] Tet[4] Tet[5]

1850年,職業数学者ではなく英国の法律家でありトーリー党(現在の保守党)の政治家でもあった初代准男爵フレデリック・ポロック卿が,すべての正整数は5個以内の正四面体数の和として表現できると予想した. ただし,和の中で同じ正四面体数が複数回出現してよく,その場合,それぞれの出現を別々に数えるものとする. この予想は一世紀半以上も未解決なままである.

あなたの任務は, 個別の整数に対してポロック予想が成り立つことを確認するプログラムを書くことである. あなたのプログラムは, 入力された整数おのおのについて, それを正四面体数の和として表すための正四面体数の個数の最小値を計算しなくてはならない. なぜか,ついでに, 奇数の正四面体数だけ使える場合の同様の計算もしなくてはならない.

たとえば, 40は2個の正四面体数の和 4×5×6 ⁄ 6 + 4×5×6 ⁄ 6 として表すことができるが, 40自体は正四面体数ではない. 40は6個の奇数の正四面体数の和 5×6×7 ⁄ 6 + 1×2×3 ⁄ 6 + 1×2×3 ⁄ 6 + 1×2×3 ⁄ 6 + 1×2×3 ⁄ 6 + 1×2×3 ⁄ 6 として表すことができるが, より少ない個数の奇数の正四面体数の和として表すことはできない. したがって,あなたのプログラムに40が与えられると, 2と6と答えなくてはならない.

Input

入力は行の並びで, おのおのの行には 106 より小さい正整数がちょうど一つだけ含まれている. 入力の終わりは,一文字の 0 だけを含む行で示される.

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

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2010-07-02
http://icpc2010.honiden.nii.ac.jp/