← 返回题目列表

Codeforces · 679/B

B. 熊和立方体塔

中文机器翻译题面 查看原题

Limak 是一只小北极熊。他玩的是用积木建造塔。每个块都是一个边长为正整数的立方体。利马克每条边长都有无限多个块。

边为 a 的块的体积为 a3。由边为 a1、a2、...、ak 的块组成的塔的总体积为 a13 + a23 + ... + ak3。

Limak 将要建造一座塔。首先,他要求你告诉他一个正整数 X——所需塔的总体积。然后,利马克贪婪地一一添加新的区块。每次他添加最大的块,使得总体积不超过X。

Limak 要求您选择 X 不大于 m。另外,他想在最后最大化塔中的方块数量(但是,他仍然表现得很贪婪)。其次,他想最大化X。

你能帮助利马克吗?求他的塔可以拥有的最大块数,以及得出该块数的最大 X ≤ m。

输入

输入的唯一一行包含一个整数 m (1 ≤ m ≤ 1015),这意味着 Limak 希望您在 1 和 m(含)之间选择 X。

输出

打印两个整数——塔中的最大块数和所需的最大总体积 X,从而得出最大块数。

示例

输入 #1

48

输出 #1

9 42

输入 #2

6

输出 #2

6 6

注意

在第一个样本测试中,如果您选择 X = 23 或 X = 42,将会有 9 个块。Limak 想要其次最大化 X,所以您应该选择 42。

更详细地说,选择 X = 42 后,建造塔的过程是:

- Limak 取了边为 3 的块,因为它是体积不大于 42 的最大块。剩余体积为 42 - 27 = 15。
- 第二个添加的块有边 2,因此剩余体积为 15 - 8 = 7。
- 最后,Limak 将边 1 的 7 个块一一添加。

所以,塔里有 9 个方块。总体积为 33 + 23 + 7·13 = 27 + 8 + 7 = 42。