Bear and Tower of Cubes

# 题目描述 Limak是一只可爱的北极熊。他正在用一堆木块搭塔。每一个木块都是一个有着正整数边长的正方体。Limak有无数块木块。显然的，每一块边长为$a$ 的木块的体积为$a^3$ ，而一个塔的体积为组成这个塔的所有木块的体积和。**这里，我们定义一个塔的高度是组成这个塔的木块数量。** Limak现在要搭建一个塔。首先，他让你告诉他一个正整数$X$ ，表示这个塔的总体积。然后，他将会贪心地搭建这个塔（每次总是尽可能地添加最大的木块，即先选一个体积最大的正方体作为第一层，第一层的体积满足体积不超过$X$ 。然后选一个最大的正方体做第二层，使得前两层的体积和满足不超过$X$ 。然后再选一个最大的正方体做第三层，使得前三层的体积和满足不超过$X$ 。依次类推，直到建好一座体积为$X$ 的塔）。 Limak想让你在$1$ - $m$ 之间选择一个$X$ ，使他能够搭建的塔的总高度$h$ 最高。同时，在总高度最高的情况下，让塔的总体积$X$ 最大。 （实在没看懂题意可以看看样例解释） # 输入输出格式 ## 输入格式 输入包含一行，一个正整数$m$ ，表示Limak想让你从$1$ 到$m$ 之间（包括$1$ 和$m$ ）选择$X$ 。 ## 输出格式 请输出一行，包含两个正整数：$h$ ，表示可以搭建出的塔的最大高度，以及$X$ ，表示当$h$ 最大时整个塔的最大体积。 # 输入输出样例 略 ## 样例说明 对于样例1，当$X=23$ 或$X=42$ 时$h$ 有最大值为9。因为Limak想让你最大化塔的体积，所以应该选择42。 在选择$X=42$ 之后，具体的建塔过程为： > - 首先，Limak选择一块边长为3的木块，因为这是体积不超过42的最大木块。剩下的体积为$42-27=15$ 。 > - 然后，同样的，Limak会选择边长为2的木块，所以剩下的体积为$15-8=7$ 。 > - 最后，Limak放上7块边长为1的木块。 所以，这座塔的高度为9，总体积为$3^3+2^3+7*1^3=27+8+7=42$ 。 感谢@星烁晶熠辉 提供的翻译

Limak is a little polar bear. He plays by building towers from blocks. Every block is a cube with positive integer length of side. Limak has infinitely many blocks of each side length. A block with side $ a $ has volume $ a^{3} $ . A tower consisting of blocks with sides $ a_{1},a_{2},...,a_{k} $ has the total volume $ a_{1}^{3}+a_{2}^{3}+...+a_{k}^{3} $ . Limak is going to build a tower. First, he asks you to tell him a positive integer $ X $ — the required total volume of the tower. Then, Limak adds new blocks greedily, one by one. Each time he adds the biggest block such that the total volume doesn't exceed $ X $ . Limak asks you to choose $ X $ not greater than $ m $ . Also, he wants to maximize the number of blocks in the tower at the end (however, he still behaves greedily). Secondarily, he wants to maximize $ X $ . Can you help Limak? Find the maximum number of blocks his tower can have and the maximum $ X<=m $ that results this number of blocks.

The only line of the input contains one integer $ m $ ( $ 1<=m<=10^{15} $ ), meaning that Limak wants you to choose $ X $ between $ 1 $ and $ m $ , inclusive.

Print two integers — the maximum number of blocks in the tower and the maximum required total volume $ X $ , resulting in the maximum number of blocks.

48

9 42

6

6 6

In the first sample test, there will be $ 9 $ blocks if you choose $ X=23 $ or $ X=42 $ . Limak wants to maximize $ X $ secondarily so you should choose $ 42 $ . In more detail, after choosing $ X=42 $ the process of building a tower is: - Limak takes a block with side $ 3 $ because it's the biggest block with volume not greater than $ 42 $ . The remaining volume is $ 42-27=15 $ . - The second added block has side $ 2 $ , so the remaining volume is $ 15-8=7 $ . - Finally, Limak adds $ 7 $ blocks with side $ 1 $ , one by one. So, there are $ 9 $ blocks in the tower. The total volume is is $ 3^{3}+2^{3}+7·1^{3}=27+8+7=42 $ .