← 返回题目列表

Codeforces · 986/D

D. 完美编码

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

您在一家公司担任分析师,致力于开发新的大数据存储系统。该系统将存储$$$n$$$不同的对象。每个对象都应该有一个唯一的 ID。

要创建系统,您需要选择系统参数 - 整数 $$$m \ge 1$$$ 和 $$$b_{1}, b_{2}, \ldots, b_{m}$$$。通过这些参数,系统中某个对象的 ID 是一个整数数组 $$$[a_{1}, a_{2}, \ldots, a_{m}]$$$,其中 $$$1 \le a_{i} \le b_{i}$$$ 对于每个 $$$1 \le i \le m$$$ 成立。

开发人员表示,生产成本与 $$$\sum_{i=1}^{m} b_{i}$$$ 成正比。系统会要求您选择参数 $$$m$$$ 和 $$$b_{i}$$$,以便系统能够为 $$$n$$$ 不同的对象分配唯一 ID,并将生产成本降至最低。请注意,您不必使用所有可用的 ID。

输入

在唯一的输入行中有一个正整数$$$n$$$。 $$$n$$$ 的十进制表示形式的长度不大于 $$$1.5 \cdot 10^{6}$$$。该整数不包含前导零。

输出

打印一个数字 - $$$\sum_{i=1}^{m} b_{i}$$$ 的最小值。

示例

输入 #1

36

输出 #1

10

输入 #2

37

输出 #2

11

输入 #3

12345678901234567890123456789

输出 #3

177