D. Perfect Encoding

Codeforces

IDCF986D

Time2000ms

Memory256MB

Difficulty—

fftmath

English · Original

Chinese · Translation

Formal · Original

You are working as an analyst in a company working on a new system for big data storage. This system will store $n$ different objects. Each object should have a unique ID. To create the system, you choose the parameters of the system — integers $m \ge 1$ and $b_{1}, b_{2}, \ldots, b_{m}$. With these parameters an ID of some object in the system is an array of integers $[a_{1}, a_{2}, \ldots, a_{m}]$ where $1 \le a_{i} \le b_{i}$ holds for every $1 \le i \le m$. Developers say that production costs are proportional to $\sum_{i=1}^{m} b_{i}$. You are asked to choose parameters $m$ and $b_{i}$ so that the system will be able to assign unique IDs to $n$ different objects and production costs are minimized. Note that you don't have to use all available IDs. ## Input In the only line of input there is one positive integer $n$. The length of the decimal representation of $n$ is no greater than $1.5 \cdot 10^{6}$. The integer does not contain leading zeros. ## Output Print one number — minimal value of $\sum_{i=1}^{m} b_{i}$. [samples]

你正在一家致力于新型大数据存储系统的公司担任分析师。该系统将存储 $n$ 个不同的对象，每个对象必须具有唯一的 ID。为设计该系统，你需要选择系统参数——整数 $m gt.eq 1$ 和 $b_1, b_2, dots.h, b_m$。使用这些参数，系统中某个对象的 ID 是一个整数数组 $[ a_1, a_2, dots.h, a_m ]$，其中对每个 $1 lt.eq i lt.eq m$，满足 $1 lt.eq a_i lt.eq b_i$。开发者表示，生产成本与 $sum_(i = 1)^m b_i$ 成正比。你需要选择参数 $m$ 和 $b_i$，使得系统能够为 $n$ 个不同对象分配唯一 ID，且生产成本最小化。注意，你不必使用所有可用的 ID。输入仅有一行，包含一个正整数 $n$。$n$ 的十进制表示的长度不超过 $1. 5 dot.op 10^6$，且不包含前导零。请输出一个数——$sum_(i = 1)^m b_i$ 的最小值。 ## Input 在输入的一行中包含一个正整数 $n$。$n$ 的十进制表示的长度不超过 $1. 5 dot.op 10^6$，且不包含前导零。 ## Output 请输出一个数——$sum_(i = 1)^m b_i$ 的最小值。 [samples]

Given a positive integer $ n $, find integers $ m \geq 1 $ and $ b_1, b_2, \dots, b_m \geq 1 $ such that: $$ \prod_{i=1}^m b_i \geq n $$ and the sum $ \sum_{i=1}^m b_i $ is minimized. --- **Objective:** Minimize $ \sum_{i=1}^m b_i $ subject to $ \prod_{i=1}^m b_i \geq n $, where $ m \in \mathbb{Z}^+ $, $ b_i \in \mathbb{Z}^+ $. --- **Note:** The $ b_i $ need not be ordered, and the product need not equal $ n $ — it suffices to be at least $ n $. The goal is to minimize the sum of the factors whose product is at least $ n $.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

12345678901234567890123456789

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Perfect Encoding",
    "description": {
      "content": "You are working as an analyst in a company working on a new system for big data storage. This system will store $n$ different objects. Each object should have a unique ID. To create the system, you c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF986D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are working as an analyst in a company working on a new system for big data storage. This system will store $n$ different objects. Each object should have a unique ID.\n\nTo create the system, you c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你正在一家致力于新型大数据存储系统的公司担任分析师。该系统将存储 $n$ 个不同的对象，每个对象必须具有唯一的 ID。\n\n为设计该系统，你需要选择系统参数——整数 $m gt.eq 1$ 和 $b_1, b_2, dots.h, b_m$。使用这些参数，系统中某个对象的 ID 是一个整数数组 $[ a_1, a_2, dots.h, a_m ]$，其中对每个 $1 lt.eq i lt.eq m$...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given a positive integer $ n $, find integers $ m \\geq 1 $ and $ b_1, b_2, \\dots, b_m \\geq 1 $ such that:\n\n$$\n\\prod_{i=1}^m b_i \\geq n\n$$\n\nand the sum $ \\sum_{i=1}^m b_i $ is minimized.\n\n---\n\n**Object...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments