F. Concise and clear

Codeforces

IDCF991F

Time2000ms

Memory256MB

Difficulty—

brute forcegreedyimplementationmath

English · Original

Chinese · Translation

Formal · Original

Vasya is a regular participant at programming contests and is already experienced in finding important sentences in long statements. Of course, numbers constraints are important — factorization of a number less than _1000000_ is easier than of a number less than _1000000000_. However, sometimes it's hard to understand the number at the first glance. Could it be shortened? For example, instead of _1000000_ you could write $10^{6}$, instead of _1000000000_ —$10^{9}$, instead of _1000000007_ — $10^{9}+7$. Vasya decided that, to be concise, the notation should follow several rules: * the notation should only consist of numbers, operations of addition ("_+_"), multiplication ("_*_") and exponentiation ("_^_"), in particular, the use of braces is forbidden; * the use of several exponentiation operations in a row is forbidden, for example, writing "_2^3^4_" is unacceptable; * the value of the resulting expression equals to the initial number; * the notation should consist of the minimal amount of symbols. Given $n$, find the equivalent concise notation for it. ## Input The only line contains a single integer $n$ ($1 \leq n \leq 10\,000\,000\,000$). ## Output Output a concise notation of the number $n$. If there are several concise notations, output any of them. [samples] ## Note The third sample allows the answer _10^10_ also of the length $5$.

Vasya 是编程竞赛的常客，已经擅长从冗长的题面中找出重要信息。当然，数值约束很重要——对一个小于 _1000000_ 的数进行因式分解，比对一个小于 _1000000000_ 的数更容易。然而，有时一眼难以理解这个数字。能否将其缩短？例如，与其写 _1000000_，不如写 $10^6$；与其写 _1000000000_，不如写 $10^9$；与其写 _1000000007_，不如写 $10^9 + 7$。 Vasya 决定，为了简洁，记法应遵循以下规则：给定 $n$，请找出它的等价简洁记法。仅一行包含一个整数 $n$（$1 lt.eq n lt.eq 10 thin 000 thin 000 thin 000$）。请输出数字 $n$ 的简洁记法。如果有多种简洁记法，输出任意一种即可。第三个样例也允许答案为 _10^10_，其长度同样为 $5$。 ## Input 仅一行包含一个整数 $n$（$1 lt.eq n lt.eq 10 thin 000 thin 000 thin 000$）。 ## Output 请输出数字 $n$ 的简洁记法。如果有多种简洁记法，输出任意一种即可。 [samples] ## Note 第三个样例也允许答案为 _10^10_，其长度同样为 $5$。

Given: $ n \in \mathbb{Z} $, $ 1 \leq n \leq 10^{10} $ Find: A concise representation of $ n $ using any of the following forms: - $ 10^k $ for some integer $ k \geq 0 $, if $ n = 10^k $ - $ 10^k + m $ for some integers $ k \geq 0 $, $ 1 \leq m < 10^k $, if $ n = 10^k + m $ - The decimal representation of $ n $ as a string (fallback) Minimize the length of the output string. If multiple concise representations exist (e.g., $ 10^{10} $ and $ 10^{10} + 0 $), output any one of minimal length.

Samples

Input #1

Output #1

Input #2

1000000007

Output #2

10^9+7

Input #3

10000000000

Output #3

100^5

Input #4

2000000000

Output #4

2*10^9

API Response (JSON)

{
  "problem": {
    "name": "F. Concise and clear",
    "description": {
      "content": "Vasya is a regular participant at programming contests and is already experienced in finding important sentences in long statements. Of course, numbers constraints are important — factorization of a n",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF991F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vasya is a regular participant at programming contests and is already experienced in finding important sentences in long statements. Of course, numbers constraints are important — factorization of a n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Vasya 是编程竞赛的常客，已经擅长从冗长的题面中找出重要信息。当然，数值约束很重要——对一个小于 _1000000_ 的数进行因式分解，比对一个小于 _1000000000_ 的数更容易。然而，有时一眼难以理解这个数字。能否将其缩短？例如，与其写 _1000000_，不如写 $10^6$；与其写 _1000000000_，不如写 $10^9$；与其写 _1000000007_，不如写 $10^...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given: $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 10^{10} $\n\nFind: A concise representation of $ n $ using any of the following forms:\n\n- $ 10^k $ for some integer $ k \\geq 0 $, if $ n = 10^k $\n- $ 10^k + ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments