{"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 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$.\n\nVasya decided that, to be concise, the notation should follow several rules:\n\n*   the notation should only consist of numbers, operations of addition (\"_+_\"), multiplication (\"_*_\") and exponentiation (\"_^_\"), in particular, the use of braces is forbidden;\n*   the use of several exponentiation operations in a row is forbidden, for example, writing \"_2^3^4_\" is unacceptable;\n*   the value of the resulting expression equals to the initial number;\n*   the notation should consist of the minimal amount of symbols.\n\nGiven $n$, find the equivalent concise notation for it.\n\n## Input\n\nThe only line contains a single integer $n$ ($1 \\leq n \\leq 10\\,000\\,000\\,000$).\n\n## Output\n\nOutput a concise notation of the number $n$. If there are several concise notations, output any of them.\n\n[samples]\n\n## Note\n\nThe third sample allows the answer _10^10_ also of the length $5$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Vasya 是编程竞赛的常客，已经擅长从冗长的题面中找出重要信息。当然，数值约束很重要——对一个小于 _1000000_ 的数进行因式分解，比对一个小于 _1000000000_ 的数更容易。然而，有时一眼难以理解这个数字。能否将其缩短？例如，与其写 _1000000_，不如写 $10^6$；与其写 _1000000000_，不如写 $10^9$；与其写 _1000000007_，不如写 $10^9 + 7$。\n\nVasya 决定，为了简洁，记法应遵循以下规则：\n\n给定 $n$，请找出它的等价简洁记法。\n\n仅一行包含一个整数 $n$（$1 lt.eq n lt.eq 10 thin 000 thin 000 thin 000$）。\n\n请输出数字 $n$ 的简洁记法。如果有多种简洁记法，输出任意一种即可。\n\n第三个样例也允许答案为 _10^10_，其长度同样为 $5$。\n\n## Input\n\n仅一行包含一个整数 $n$（$1 lt.eq n lt.eq 10 thin 000 thin 000 thin 000$）。\n\n## Output\n\n请输出数字 $n$ 的简洁记法。如果有多种简洁记法，输出任意一种即可。\n\n[samples]\n\n## Note\n\n第三个样例也允许答案为 _10^10_，其长度同样为 $5$。","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 + m $ for some integers $ k \\geq 0 $, $ 1 \\leq m < 10^k $, if $ n = 10^k + m $\n- The decimal representation of $ n $ as a string (fallback)\n\nMinimize the length of the output string.\n\nIf multiple concise representations exist (e.g., $ 10^{10} $ and $ 10^{10} + 0 $), output any one of minimal length.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF991F","tags":["brute force","greedy","implementation","math"],"sample_group":[["2018","2018"],["1000000007","10^9+7"],["10000000000","100^5"],["2000000000","2*10^9"]],"created_at":"2026-03-03 11:00:39"}}